ITL
© 1996-2018







II.3 Examples Propositional Logic

Propositional Logic Examples [Slide 23]

Example 1.

true
¬P
true P
false ¬P
false P
P (P R)

Propositional Logic Examples [Slide 24]

Example 2.

Let P denote the proposition “The moon is made of cheese”

Let Q denote the proposition “The moon is red”

The sentence “If the moon is red, it is not made of cheese” is translated as propositional formula Q (¬P)

Truth Table: And [Slide 25]




P
Q
P Q



false
false
false
false
true
false
true
false
false
true
true
true



true iff (if and only if) both operands are true

Truth Table: Or [Slide 26]




P
Q
P Q



false
false
false
false
true
true
true
false
true
true
true
true



true iff (if and only if) either operands are true

Truth Table: Not [Slide 27]



P
¬P


false
true
true
false


true iff operand is false.

Truth Table: Implication [Slide 28]




P
Q
P Q



false
false
true
false
true
true
true
false
false
true
true
true



true iff first is true and second is true or the first is false.

Truth Table: Equivalence [Slide 29]




P
Q
P Q



false
false
true
false
true
false
true
false
false
true
true
true



true iff both operands have the same value.

Semantic Reasoning: Truth tables [Slide 30]

  • From truth table take into account ALL its constituents. The formula P ((¬P) Q) has the following constituents ¬P, (¬P) Q as well as P and Q.






P
Q
¬P
(¬P) Q
P ((¬P) Q)





false
false
false
true
true
false
true
true





  • The values in the last column determine the value of the proposition:
    • if some values are true, the proposition is known to be satisfiable
    • if the values are all true, the proposition is valid
    • if all are false, the proposition is not satisfiable (contradiction).

Reasoning with Truth table [Slide 31]

  • Works fine when there are 2 variables: 4 lines in the table.
  • three variables: 8 lines in the table.
  • 20 variables is definitely out of hand: 220 lines in the table. You don’t want to look at a million lines, and if you do, you will make mistakes!
  • Hundreds of variables - not in a million years.
  • There are other ways to reason, but outside the scope of this course.







2018-03-10
Contact | Home | ITL home | Course | Proofs | Algebra | FL