Logic and Discrete Mathematics Exam Help

From ICO wiki
Jump to navigationJump to search

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∨TT
p∧FF
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

A predicate or propositional function is a description of the property (or properties) a variable or subject may have. A proposition may be created from a propositional function by either assigning a value to the variable or by quantification. Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language.

Example: 
Having assumptions:
•	Every computer connected to the school network is functioning properly.
•	ELVIS is one of the computers connected to the school network.
No rules of propositional logic allows us to conclude the truth of the statement
 ELVIS is functioning properly

Extends propositional logic by • Individuals a, b, ... , ELVIS, ...

• (Individual) variables x,y,...

• Predicates(= propositional functions) P(x), Q(x), R(x,y), ...

• Quantifiers ∀,∃

A propositional function is a generalisation of proposition: • its argument stands for en element from its domain;

• its value is True or False depending on the property of its argument(s).

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.

Logical equivalences for quantifiers

Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

Examples

Example where ∀x.∃y.P(x,y) (¬≡) ∃y.∀x.P(x,y)

The meaning of the different possible quantifications involving two varialbes.

Propositional calculus (PC)

Derivation in classical logic

Semantics of predicate calculus

Validity and satisfiability of predicate statements

Validity

An assertion in predicate calculus is logically valid (or simply valid) if it is true in every interpretation, that is if and only if it is true :

- for all domains

- for every propositional functions substituted for the predicates in the assertion

Valid assertions in predicate logic play a role similar to tautologies in propositional logic.

Example:

∀x.(P(x)v¬P(x))

Satisfiability

An assertion in predicate calculus is satisfiable iff it is true:

- for some domain

- for some propositional functions that can be substituted for the predicates in the assertion

Valid assertions in predicate logic play a role similar to tautologies in propositional logic. Example: link

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).

Proof techniques. Constructive and non-constructive proofs

Proofs by contraposition and contradiction

Mathematical induction (ordinary and strong)

Recursively defined functions

Elementary set theory, basic definitions and set operations

Power set and Cartesian product

Cardinality. Countable sets

Countability of rational numbers

Uncountable sets

Cardinality of power set

Continuum hypothesis

Binary relations

Equivalence relation

Partial order relation

Composition of relations, powers of relations

Closures of relations

Functions

Injective, surjective and bijective functions

Basic counting techniques

Product rule

Sum rule

Inclusion-exclusion principle

Pigeon-hole principle

Combinations and permutations

Binomial coefficients

Pascal's triangle

Permutations of multisets

Distributing n identical objects among k groups. Combinations with repetitions

Recurrence equations

Classification

Arithmetic and geometric progressions

Fibonacci sequence

Method of characteristic roots for solving of recurrence equations

Graphs, vertices, edges, paths, cycles and connectedness

Eulerian and Hamiltonian graphs, travelling-salesman problem

The shortest path problem

Dijkstra’s algorithm

Basic definitions and properties of trees

Minimum spanning tree problem

Kruskal’s algorithm

Isomorphism of labelled graphs

Prüfer’s code

Number of labelled trees

Counting of unlabelled trees

Planar graphs. Euler’s formula

Homeomorphic graphs

Characterization of planar graphs

Platonic solids and planar graphs

Colouring of graphs

Brooks’ theorem

Welch-Powell’s colouring algorithm

Colouring of planar graphs with 6 and 5 colours

Colouring of maps and four-colour problem