CHAPTER ONE - LOGIC AND PROOFS

Propositional Logic

Proposition Logic  - Sentence that declare fact either true or false but not both .


Example :
i  ) F and S is alphabet ( true )

ii ) They are beautiful   ( false )
    - (ii) is not proposition because not declarative statement .

iii ) 2 + 1 = 10            ( true )

iv ) x + y = 3              ( false )
     -(iv) is not proposition because they are neither true or false .


Propositional Variables - Use letters to represent propositions.


Truth tables - Truth tables shows the relationship between the truth values of

                        propositions and compound propositions formed from propositions.


Types of truth table :

TABLE 1 The Truth Table for Negation of a Proposition.
p	¬ p
T       F	F       T

 Let p be the proposition. The statement  "It is not the case that p" is another proposition, called the negation of p. The negation of p is denoted by ¬ p. The proposition ¬ p is read "not p".

TABLE 2 The Truth Table for The Conjunction of Two Propositions.
p            q	p  Ʌ  q
T            T       T            F       F            T       F            F	T           F           F           F

Let p and q be propositions. The proposition "p and q",denoted  p Ʌ q, is the proposition that is true when both p and q are true and is false otherwise. The proposition p  Ʌ  q is called the conjunction of p and q.

TABLE 3 The Truth Table for The Disjunction of Two Propositions.
p            q	p  V  q
T            T       T            F       F            T       F            F	T           T           T           F

 







Let p and q be propositions. The proposition "p or q", denoted  p  V  q, is the proposition that is false when both p and q are false and is true otherwise. The proposition p  V  q is called the disjunction of p and q.

TABLE 4 The Truth Table for The Exclusive Or of Two Propositions.
p            q	p Å q
T            T       T            F       F            T       F            F	F           T           T           F

 







Let p and q be propositions. The exclusive or of  p and q,denoted p Å q, is the proposition that is true when exactly one of p and q is true and is false otherwise.

TABLE 5 The Truth Table for The Implication p → q
p            q	p  →  q
T            T       T            F       F            T       F            F	T           F           T           T

 






Let p and q be propositions. The implication p → q is the proposition that is false when p is true and q is false and is true otherwise. In this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequences).

TABLE 6 The Truth Table for The Biconditional p ↔ q
p            q	p  ↔  q
T            T       T            F       F            T       F            F	T           F           F           T

Let p and q be propositions. The biconditional  p ↔ q  is the proposition that is true when both p and q have the same truth values,and is false otherwise.

TABLE 7 Precedence of Logical Operators.
operator	precedence
¬	1
Ʌ          V	2            3
→          ↔	4            5

TABLE 8 Table for the Bit Operators OR, AND and XOR .
x	y	x V y	x Ʌ y	x Å y
0       0       1       1	0       1       0       1	0       1       1       1	0       0       0       1	0        1        1        0