CS1502 Formal Methods in
Computer Science
Lecture Notes 4
Tautologies and Logical Truth
1
, Constructing a Truth Table
Write down sentence
Create the reference columns
Until you are done:
– Pick the next connective to work on
– Identify the columns to consider
– Fill in truth values in the column
EG: ~(A ^ (~A v (B ^ C))) v B
(in Boole and on board)
2
, Tautology
A sentence S is a tautology if and only if
every row of its truth table assigns true to
S.
3
Computer Science
Lecture Notes 4
Tautologies and Logical Truth
1
, Constructing a Truth Table
Write down sentence
Create the reference columns
Until you are done:
– Pick the next connective to work on
– Identify the columns to consider
– Fill in truth values in the column
EG: ~(A ^ (~A v (B ^ C))) v B
(in Boole and on board)
2
, Tautology
A sentence S is a tautology if and only if
every row of its truth table assigns true to
S.
3
