Propositional Logic

Propositions

◼
  • What is a proposition?
    • ◼
  • A proposition (also a statement) is a sentence to which a truth value (True or False for the purpose of this course) can be assigned to.
    • ◼
  • Examples:
    • ◼
  • The sky is blue.
    • ◼
  • There will be rain tomorrow.
    • ◼
  • He said that he would be there.
    • ◼
  • My favorite food is bread.
    • ◼
  • Each of the examples above is a full sentence(i.e. it has a subject and a predicate) that can be assigned a truth value.
    • ◼
  • Non-examples:
    • ◼
  • The blue sky. (Not a full sentence as it is missing a verb)
    • ◼
  • Bring me a cup! (Not a statement to which a truth value can be assigned)
    • ◼
  • So to reiterate in order to check f something is a proposition (statement) you need to check two things:
    • 1
    .
    Is it a sentence?
    2
    .
    Does it make sense to assign to it a truth value?

    Logical Connectors

    ◼
  • Logical connectors allow us to combine propositions into more complex ones.

    • The negation (not ...)

    ◼
  • The negation of a proposition is built by prepending the “not” connector, usually denoted by the symbol ¬
    • ◼
  • If p is a proposition, then ¬p (read as “not p”)is the negation of p.
    • ◼
  • If p has the value True then the negation will have the value False.
    • ◼
  • If p has the value False then the negation will have the value True.

    • The disjunction (...or...)

    ◼
  • The disjunction of two propositions is built by using the “or” connector usually denoted by the symbol ∨
    • ◼
  • If p and q are propositions, then p ⋁ q (read as “p or q”) is the disjunction of p and q.
    • ◼
  • If either of p or q have the truth value True then the disjunction p ∨ q will have the truth value True.
    • ◼
  • In the case that both p and q are False the disjunction p ⋁ q will have the value False.

    • The conjunction (...and...)

    ◼
  • The conjunction of two propositions is built by using the “and” connector usually denoted by the symbol ∧
    • ◼
  • If p and q are propositions, then p ∧ q (read as “p and q”) is the conjunction of p and q.
    • ◼
  • If either of p or q have the truth value False, then the conjunction p ∧ q will have the truth value False.
    • ◼
  • In the case that both p and q are True the conjunction p ∧ q will have the value True.

    • The implication or conditional (if..., then ... | ...implies...)

    ◼
  • The implication of two propositions is built using the “if... then...” connector, usually denoted by ⟶(or sometimes )
    • ◼
  • If p and q are propositions, then pq (read as “if p, then q” or as “p implies q”) is the implication of q by p.
    • ◼
  • If either p has the truth value False or if q has the truth value True, then the implication pq will have the truth value True.
    • ◼
  • If p has the truth value True and q has the truth value False, then the implication pq has the truth value False.
    • ◼
  • If the implication pq is true, we usually say that p is a sufficient condition for q.
    • ◼
  • Given an implication pq, there are a couple of constructs that are associated to it.
    • ◼
  • The converse of pq, is the implication qp.
    • ◼
  • The contrapositive of pq, is the implication (¬q)(¬p).
    • ◼
  • The inverse of pq, is the implication (¬p¬q).

    • The biconditional or equivalence (... if, and only if,... | ... is equivalent to...)

    ◼
  • The biconditional of two propositions is built using the “if and only if” connector, usually denoted by (or sometimes ⟺).
    • ◼
  • If p and q are propositions, then pq (read as “p if, and only if, q” or as “p is equivalent to q”) is the biconditional of p and q.
    • ◼
  • If both p and q have the same truth value, then the biconditional pq has the truth value True.
    • ◼
  • If p and q have different truth values, then the biconditional pq has the truth value False.

    • Extra Notes

    ◼
  • If we are being formal we would consider a set A which we would call atomic propositions from which we build the more complex cases.
    • ◼
  • By combining several connectives we can build more complex propositions.
    For example:
    • ◼
  • ¬p∨q↔pq
    • ◼
  • normally we would add the use of parenthesis “(“ and “)” to make clear what is the intended “order” in which to read the statement above. For example((¬p)∨q)↔(pq)
    • ◼
  • In the interest of formality we should be thinking of the connectors as functions whose arguments are propositions and their values are also propositions.
    • ◼
  • With this in mind, ¬ would be a unary function, while ∧, ∨, , and  will be considered binary functions.
    • ◼
  • With this in mind, propositions should be written in functional notation. Where, for example, p∧q would be written as ∧(p,q), or the more abbreviated “prefixed” or “Polish” notation ∧pq.
    • ◼
  • The advantage with the prefixed notation is that we would have no ambiguity when it comes to “order of operations”.
    • ◼
  • ¬p∨q↔pq could be interpreted as ((¬p)∨q)↔(pq) or as ¬((p∨q)↔(pq)). Whereas in Polish notation we would have ∨¬pqpq for the first interpretation, and ¬∨pqpq for the second.
    • ◼
  • Some programing languages use this prefixed notation to parse inputs and interpret them.(LISP)
    • ◼
  • The disadvantage with prefixed notation is that it is less human-readable than with the common notation using parenthesis
    • ◼
  • Even though there is no universally accepted “order of boolean operations” in the traditional notation, it is fairly accepted that ¬ has precedence, so ((¬p)∨q)↔(pq) can be simply written as (¬p∨q)↔(pq), where we understand that the first negation is only affecting the p it precedes.
    • ◼
  • We will use the convention that ¬ has precedence but every other ambiguous proposition should be cleared with the use of parenthesis when written in traditional form.

    • Truth Tables

    Out[]=
    p
    q
    p∧q
    True
    True
    True
    True
    False
    False
    False
    True
    False
    False
    False
    False
    ◼
  • The array above is what we call a truth table for the proposition p∧q, that is the conjunction.
    • ◼
  • A truth table for a proposition is a table as the one above that determines the truth value of a proposition depending on the truth value of their atoms
    • ◼
  • In the interest of being succinct we sometimes use the abbreviations T and F for True and False respectively as is shown below.
    • Out[]=
    p
    q
    p∧q
    T
    T
    T
    T
    F
    F
    F
    T
    F
    F
    F
    F
    ◼
  • The following will be the truth tables for the propositions obtained by one iteration of the logical connectives mentioned before
    • ◼
  • Disjunction
    • Out[]=
    p
    q
    p∨q
    True
    True
    True
    True
    False
    True
    False
    True
    True
    False
    False
    False
    ◼
  • Implication
    • Out[]=
    p
    q
    pq
    True
    True
    True
    True
    False
    False
    False
    True
    True
    False
    False
    True
    ◼
  • Equivalence
    • Out[]=
    p
    q
    p⧦q
    True
    True
    True
    True
    False
    False
    False
    True
    False
    False
    False
    True
    ◼
  • Negation
    • Out[]=
    p
    ¬p
    True
    False
    False
    True
    ◼
  • We can of course build a truth table for more complex propositions.
    • Out[]=
    p
    q
    ((¬p)∨q)↔(pq)
    True
    True
    True
    True
    False
    True
    False
    True
    True
    False
    False
    True
    Out[]=
    p
    q
    r
    (p∨q∨r)(p∨(q⧦r))
    True
    True
    True
    True
    True
    True
    False
    True
    True
    False
    True
    True
    True
    False
    False
    True
    False
    True
    True
    True
    False
    True
    False
    False
    False
    False
    True
    False
    False
    False
    False
    True
    ◼
  • Notice how in the last table, and in the negation we had a different number of rows compared to the number of rows in the truth table for the disjunction, conjunction, implication and equivalence.
    • ◼
  • What determines the number of rows in a truth table?

    • Equivalent Propositions

    ◼
  • We say that two propositions are logically equivalent if their truth values are the same in every case.
    • ◼
  • A surefire way of telling if two propositions are equivalent is by checking their truth tables. If their truth tables are the same, then they are logically equivalent statements.

    • Tautologies

    ◼
  • A tautology is a proposition whose truth value is True independent of the truth value of its atoms.
    For example:
    • ◼
  • p→p
    • ◼
  • p∨¬p
    • ◼
  • ((p→q)∧p)→q
    • ◼
  • Check that the above are tautologies by building their truth tables.
    • ◼
  • There is a connection between equivalence (the logical connector), logical equivalence (the property of propositions), and tautologies. If two propositions are logically equivalent then the equivalence between them is a tautology.
    • ◼
  • An example that we saw before was ((¬p)∨q)↔(pq).
    • ◼
  • As such we shall sometimes use “equivalent” and “logically equivalent” interchangeably.

    • DeMorgan’s Laws

    ◼
  • A very commonly known set of equivalent propositions are:
    • ◼
  • ¬(p∨q) is equivalent to ¬p∧¬q
    • ◼
  • ¬(p∧q) is equivalent to ¬p∨¬q
    • ◼
  • The equivalences above are referred to as DeMorgan’s Laws
    • ◼
  • It is simple to proof them by using truth tables
    • ◼
  • Do the same for the second of DeMorgan’s Laws.

    • Applications

    ◼
  • An advantage of equivalent propositions is that we can abbreviate complex propositional expressions or simplify them to logically equivalent ones.
    • ◼
  • For example ¬¬p is logically equivalent to p.
    • ◼
  • This leads to an interesting result:
    • 1
    .
    Show that given any nonempty set of propositions A the number of propositions we can build from A is infinite.
    2
    .
    Show that regardless of having an infinite number of propositions, if A is finite, then the number of distinct propositions under equivalency is finite.
    ◼
  • For example, with one proposition we can build only 4 non equivalent propositions
    • ◼
  • Can you find propositions for each of the truth tables above?
    • Exercises