The Foundations: Logic and Proof, Sets, and Foundations PROPOSITIONS A proposition is a declarative sentence that is either True or False, but not the. - ppt download

$ 22.99

4.9 (679) In stock

Logical Connectives OperatorSymbolUsage Negation  not Conjunction  and Disjunction  or Exclusive or  xor Conditional  if,then Biconditional  iff
Example: 1. Washington is the capital of United states of America, 2. Toronto is the capital of Canada = = 3 Proposition 1 and 3 are True whereas 2 and 4 are False..
What time is it. 2. Read this carefully. 3. x+1 = 2 4. x+y = 3 1 and 2 are not Propositions because they are not declarative sentences. 3 and 4 are not Propositions because they are neither True nor False. Truth value of proposition is true, denoted by T and truth value of proposition is false denoted F. The area of logic that deals with propositions is called the propositional calculus or propositional logic. Developed by the Greek philosopher Aristotle 2300 years back..
Compound Propositions: Examples p = Cruise ships only go on big rivers. q = Cruise ships go on the Hudson. r = The Hudson is a big river.  r = The Hudson is not a big river. p  q = Cruise ships only go on big rivers and go on the Hudson. p  q  r = If cruise ships only go on big rivers and go on the Hudson, then the Hudson is a big river.
EG: p = 23 = p happens to be false, so  p is true..
Here is the truth table for negation: p pp FTFT TFTF.
On the other hand, negation is a unary operator (the only non-trivial one possible)..
I.e., for p and q to be true, it must be the case that BOTH p is true, as well as q. If one of these is false, than the compound statement is false as well..
p = Clinton was the president. q = Hilary was the president. r = The meaning of is is important. Assuming p and r are true, while q false. Out of p  q, p  r, q  r only p  r is true..
Conjunction – truth table pq pqpq TTFFTTFF TFTFTFTF TFFFTFFF
Disjunction – truth table Conversely, disjunction is true when at least one of the components is true: pq pqpq TTFFTTFF TFTFTFTF TTTFTTTF
p = Clinton was the president. q = Hilary was the president. r = The meaning of is is not important. Assuming p is true, while q and r are false. Out of p  q, p  r, q  r only q  r is false..
Review NOT, AND, OR What is the disjumction --- or What is the conjunction – and Negation – not Construct the TT for all above
Most restaurants definitely don’t allow you to get both soup and salad so that the statement is false when both soup and salad is served. To address this situation, exclusive-or is introduced next..
Exclusive-Or – truth table pq p  q TTFFTTFF TFTFTFTF FTTFFTTF
It’s only partly akin to the English usage of if, then or implies . DEF: p  q is true if q is true, or if p is false. In the final case (p is true while q is false) p  q is false. Semantics: p implies q is true if one can mathematically derive q from p..
Conditional -- truth table pq p  q TTFFTTFF TFTFTFTF TFTTTFTT
The biconditional P ↔ Q is the proposition that is True when P and Q have the same truth values, and is False otherwise. P if and only if Q P→Q and Q→ P P is necessary and sufficient for Q.
Biconditional truth table PQ P ↔Q TTFFTTFF TFTFTFTF TFFTTFFT
Q: It is snowing. Express each of these propositions as an English sentences P  Q, P  Q,  P  Q, P  Q, P→Q, P↔Q Answers: It is below freezing and snowing. It is below freezing but not snowing. It is not below freezing and it is not snowing. It is below freezing or snowing. If it is below freezing then it is snowing. It is below freezing iff it is snowing.
Propositional Equivalences
EG: p  ¬ p (Law of excluded middle) The opposite to a tautology, is a compound proposition that ’ s always false – a contradiction. EG: p  ¬ p On the other hand, a compound proposition whose truth value isn ’ t constant is called a contingency. EG: p  ¬ p.
TFTF FTFT pp p TTTT p  p TFTF FTFT pp p FFFF p  p.
Tautology example Demonstrate that [ ¬ p  (p  q )]  q is a tautology in two ways: 1.Using a truth table – show that [ ¬ p  (p  q )]  q is always true 2.Using a proof (will get to this later).
Tautology by truth table pq ¬p¬p p  q ¬ p  (p  q )[ ¬ p  (p  q )]  q TT TF FT FF
Tautology by truth table pq ¬p¬p p  q ¬ p  (p  q )[ ¬ p  (p  q )]  q TTF TFF FTT FFT
Tautology by truth table pq ¬p¬p p  q ¬ p  (p  q )[ ¬ p  (p  q )]  q TTFT TFFT FTTT FFTF
Tautology by truth table pq ¬p¬p p  q ¬ p  (p  q )[ ¬ p  (p  q )]  q TTFTF TFFTF FTTTT FFTFF
Tautology by truth table pq ¬p¬p p  q ¬ p  (p  q )[ ¬ p  (p  q )]  q TTFTFT TFFTFT FTTTTT FFTFFT
Logical equivalence is denoted by p  q. EG: The contrapositive of a logical implication is the reversal of the implication, while negating both components. I.e. the contrapositive of p  q is ¬ q  ¬ p. As we ’ ll see next: p  q  ¬ q  ¬ p.
¬q¬p¬q¬p p ¬p¬pq ¬q¬q.
TTFFTTFF ¬q¬p¬q¬p p ¬p¬p TFTFTFTF q ¬q¬q.
TTFFTTFF ¬q¬p¬q¬p p ¬p¬p TFTFTFTF q FTFTFTFT ¬q¬q.
TTFFTTFF ¬q¬p¬q¬p p FFTTFFTT ¬p¬p TFTFTFTF q FTFTFTFT ¬q¬q.
TFTTTFTT TTFFTTFF ¬q¬p¬q¬p p FFTTFFTT ¬p¬p TFTFTFTF q FTFTFTFT ¬q¬q.
Furthermore, the biconditional is true exactly when the truth values of p and of q are identical. So if the last column of truth tables of p and of q is identical, the biconditional join of both is a tautology..
I.e. the converse of p  q is q  p. EG: The converse of If Donald is a duck then Donald is a bird. is If Donald is a bird then Donald is a duck. As we ’ ll see next: p  q and q  p are not logically equivalent..
Logical Non-Equivalence of Conditional and Converse pq p  qq  p(p  q)  (q  p)
Logical Non-Equivalence of Conditional and Converse pq p  qq  p(p  q)  (q  p) TTFFTTFF TFTFTFTF
Logical Non-Equivalence of Conditional and Converse pq p  qq  p(p  q)  (q  p) TTFFTTFF TFTFTFTF TFTTTFTT
Logical Non-Equivalence of Conditional and Converse pq p  qq  p(p  q)  (q  p) TTFFTTFF TFTFTFTF TFTTTFTT TTFTTTFT
Logical Non-Equivalence of Conditional and Converse pq p  qq  p(p  q)  (q  p) TTFFTTFF TFTFTFTF TFTTTFTT TTFTTTFT TFFTTFFT
Derivational Proof Techniques When compound propositions involve more and more atomic components, the size of the truth table for the compound propositions increases Q1: How many rows are required to construct the truth-table of: ( (q  (p  r ))  (  (s  r)  t) )  (  q  r ) Q2: How many rows are required to construct the truth-table of a proposition involving n atomic components
Checking for tautologies/logical equivalences of complex propositions can become a chore, especially if the problem is obvious..
Derivational Proof Techniques EG: consider the compound proposition (p  p )  (  (s  r)  t) )  (  q  r ) Q: Why is this a tautology
Derivational Proof Techniques A: Part of it is a tautology (p  p ) and the disjunction of True with any other compound proposition is still True: (p  p )  (  (s  r)  t ))  (  q  r )  T  (  (s  r)  t ))  (  q  r )  T Derivational techniques formalize the intuition of this example.
Tables of Logical Equivalences Identity laws Like adding 0 Domination laws Like multiplying by 0 Idempotent laws Delete redundancies Double negation I don ’ t like you, not Commutativity Like x+y = y+x Associativity Like (x+y)+z = y+(x+z) Distributivity Like (x+y)z = xz+yz De Morgan
Tables of Logical Equivalences Excluded middle Negating creates opposite Definition of implication in terms of Not and Or
DeMorgan Identities DeMorgan ’ s identities allow for simplification of negations of complex expressions Conjunctional negation:  (p 1  p 2  …  p n )  (  p 1  p 2  …  p n ) Disjunctional negation:  (p 1  p 2  …  p n )  (  p 1  p 2  …  p n )
Tautology example (1.2.8.a) Part 2 Demonstrate that [ ¬ p  (p  q )]  q is a tautology in two ways: 1.Using a truth table (did above) 2.Using a proof.
Tautology by proof [ ¬ p  (p  q )]  q
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan  [p  ¬ q ]  q Double Negation
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan  [p  ¬ q ]  q Double Negation  p  [ ¬ q  q ] Associative
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan  [p  ¬ q ]  q Double Negation  p  [ ¬ q  q ] Associative  p  [q  ¬ q ] Commutative
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan  [p  ¬ q ]  q Double Negation  p  [ ¬ q  q ] Associative  p  [q  ¬ q ] Commutative  p  T ULE
Tautology by proof [ ¬ p  (p  q )]  q  [( ¬ p  p)  ( ¬ p  q)]  qDistributive  [ F  ( ¬ p  q)]  q ULE  [ ¬ p  q ]  q Identity  ¬ [ ¬ p  q ]  q ULE  [ ¬ ( ¬ p)  ¬ q ]  q DeMorgan  [p  ¬ q ]  q Double Negation  p  [ ¬ q  q ] Associative  p  [q  ¬ q ] Commutative  p  T ULE  T Domination
Exercises Construct the truth table for the following Propositions: 1, (P  Q) →Q 2, (P  Q) →(P  Q) 3, (P→Q)  (  P→  Q) 4, (P  Q)  (P  Q) 5, (P↔Q)  (P↔  Q) Show that the following by constructing the truth table: 1, (P↔Q)  (P→Q)  (Q→P) 2, (P→Q)  P  Q 3, P  (Q  R)  (P  Q)  (P  R)
Show that [  P  (P  Q)]→Q is a tautology. Determine whether the proposition [  P  (P → Q)]→Q is a tautology or not. Determine whether the proposition [P  (P → Q)]→Q is a tautology or not. Determine whether the proposition [  Q  (P → Q)]→  Q is a tautology or not. Show that  (P→Q)→  Q is a tautology. Show that  (P→Q)→  P is a tautology. Show that  (P  (  P  Q)) and  P  Q are logically equivalent..