Logic and Discrete Mathematics Exam Help

I601 Logic and Discrete Math Revision Questions

Propositions, logical operations and compound propositional statements

A proposition is a declarative sentence that is either true or false, but not both. A proposition can also be considered a result of logical operators (logical connectives, AND, OR, XOR, NAND, IF THEN, IFF). New compositions, called compound propositions are formed from existing propositions using logical operators.

Classification of compound propositions

Satisfiability

A proposition is satisfiable if truth table contains True at least once.

Tautology

A proposition is a tautology if is always true (truth table consists of value True).

Contradiction

If the truth table is always false.

Contingency

A proposition is satisfiable but not a tautology.

Logical equivalence

If two propositions, p and q, have the same value in all possible cases are called logically equivalent, p ≡ q, if p↔q.

Equivalence	Name
p∧T≡p p∨F≡p	Identity laws
p∨T≡T p∧F≡F	Domination laws
p∨p≡p p∧p≡p	Idempotent laws
¬(¬p)≡p	Double negation law
p∨q≡q∨p p∧q≡q∧p	Commutative laws
(p∨q)∨r≡p∨(q∨r) (p∧q)∧r≡p∧(q∧r)	Associative laws
p∨(q∧r)≡(p∨q)∧(p∨r) p∧(q∨r)≡(p∧q)∨(p∧r)	Distributive laws
¬(p∧q)≡¬p∨¬q ¬(p∨q)≡¬p∧¬q	De Morgan's laws
p∨(p∧q)≡p p∧(p∨q)≡p	Absorption laws
p∨¬p≡T p∧¬p≡F	Negation laws

Contrapositive

The negative version of the positive logical proposition, p∨q≡¬p∧¬q.

Converse

The mirror opposite of a logical proposition.

p	q	p→q	q→p
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

Algebra of propositions

Laws of Algebra of propositions The table can be found here: Table: Laws of Algebra of Propositions (you can just add this picture and delete this all:D)

About Truth Table:

To be T they have to be:
  Λ               == both True
  V               == at least 1 True
  p → q           == p ≡ False or q ≡ True
  p ↔ q           == both False or True

Identity:

p V p ≡ p          p Λ p ≡ p          p → p ≡ T          p ↔ p ≡ T	
p V T ≡ T          p Λ T ≡ p          p → T ≡ T          p ↔ T ≡ p	
p V F ≡ p          p Λ F ≡ F          p → F ≡ ~p        p ↔ F ≡ ~p
                        T → p ≡ p	
                        F → p ≡ T

Commutative:

p V q ≡ q V p          p Λ q ≡ q Λ p          p → q ≠ q → p          p ↔ q ≡ q ↔ p

Complement:

p V ~p ≡ T          p Λ ~p ≡ F          p → ~p ≡ ~p          p ↔ ~p ≡ F
                                                    ~p → p ≡ p	

Double Negation:

~(~p) ≡ p

Associative:

p V (q V r) ≡ (p V q) V r	
p Λ (q Λ r) ≡ (p Λ q) Λ r	

Distributive:

p V (q Λ r) ≡ (p V q) Λ (p V r)	
p Λ (q V r) ≡ (p Λ q) V (p Λ r)		

Absorbtion:

p V (p Λ q) ≡ p			
p Λ (p V q) ≡ p		

De Morgan’s:

~(p V q) ≡ ~p Λ ~q	
~(p Λ q) ≡ ~p V ~q	

Equivalence of Contrapositive:

p → q ≡ ~q → ~p	

Others:

p → q ≡ ~p V q	
p ↔ q ≡ (p → q) Λ (q → p)

Conjunctive and Disjunctive Normal Form of propositional statements

A formula in conjunctive normal form (CNF) is a conjunction of clauses.

Example of CNF: (p∨¬q∨r)∧(¬p∨¬r)∧q 

Similarly, one defines formulas in disjunctive normal form (DNF) by swapping the words ’conjunction’ and ’disjunction’ in the definitions above.

Example of DNF: (¬p∧q∧r)∨(¬q∧¬r)∨(p∧r) 

Transformation into CNF : Every propositional formula can be converted into an equivalent formula that is in CNF.

Example: Transform the following formula into CNF: ¬(p → q) ∨ (r → p)
1) Express implication by disjunction and negation:  ¬(¬p∨q) ∨ (¬r ∨ p)
2) Push implication by disjunction and negation:  (¬¬p∧¬q) ∨ (¬r ∨ p); (p∧¬q) ∨ (¬r ∨ p)
3) Convert to CNF by associative and distributive laws: (p∨¬r ∨ p)∧(¬q¬r ∨ p)
4) Optionally simplify by commutative and idempotent laws: (p∨¬r)∧(¬q(p∨¬r)
    and by commutative and absorption laws: p∨¬r

Predicates and quantifiers

Bound and free variables

• The quantifiers are said to bind the variable x in the expressions ∀xP(x) and ∃xP(x). Variables in the scope of some quantifier are called bound variables. All other variables in the expression are called free variables.

• A propositional function that does not contain any free variables is a proposition and has a truth value.

Sequent predicate calculus LK

A way of deducing if a logic statement is true or not. Please see yourself to the interactive tutorial of the Sequent Calculus (LK).