Local Attacks

1. Propositions, logical operations and compound propositional statements

• What is Propositions?

            A proposition (or statement) is a declarative statement that is either true (T) or false (F), but not both. 
            

Example: the cloud in sky, 3+1=4

• Axiom?

An axiom is a proposition that is assumed to be true (T) • Logical operation & Compound propositional statements.?

Many propositions are composite, that is, composed of sub-propositions and various connectives (see below). Such composite propositions are called compound propositions “and ,” and “or,” above are examples of connectives (logical operations)

p and q are propositional variables or (statement variables), that is, variables that

represent propositions, just as letters are used to denote numerical variables

Compound propositions can be constructed from other propositions using the following logical

connectives:

Negation: : ¬

Conjunction: ∧

Disjunction: ∨

Implication: →

Biconditional: ↔

2. Classification of compound propositions: tautology, contradiction, contingency, logical equivalence, contrapositive, converse.

A proposition is satisfiable if its truth table contains the value T at least once.

A proposition is a tautology if it is always true.

A proposition is a contradiction if it is always false.

A proposition is a contingency if it is satisfiable but not a tautology

Two propositions p and q are logically equivalent, denote p ≡ q, if p ↔ q .

                             Example 1: p 𠪪 p. 

                              Example 2: p → q ≡ ¬ p ∨ q. 

Let p and q denote two arbitrary propositions, the proposition ¬q → ¬p is the contrapositive of the proposition p → q.

Let p and q denote two arbitrary propositions, the proposition q → p is the converse of the proposition p → q.

                              Proposition: q → p 6≡ p → q

3. Algebra of propositions.

Domination laws p ∨ T ≡ T , p ∧ F ≡ F

Identity laws p ∧ T ≡ p , p ∨ F ≡ p

Idemp otent laws p ∧ p ≡ p , p ∨ p ≡ p

Involution law ¬(¬p) ≡ p

Complement laws p ∨ (¬p) ≡ T , p ∧ (¬p) ≡ F

Commutative laws p ∨ q ≡ q ∨ p , p ∧ q ≡ q ∧ p

Asso ciative laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) , (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive law s p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) , p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

Absorption laws p ∨ (p ∧ r) ≡ p , p ∧ (p ∨ r) ≡ p

DeMorgan laws ¬(p ∧ q) ≡ ¬p ∨ ¬q , ¬(p ∨ q) ≡ ¬p ∧ ¬q

A logical equivalence can b e proved by constructing the truth tables.

Known logical equivalences can b e used to prove new logical equivalences

4. Conjunctive and Disjunctive Normal Form of propositional statements.

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

A formula in disjunctive normal form (CNF) is a disjunction of clauses. 

Transform the following formula into CNF: ¬( p → q) ∨ ( r → p)

1. Express implication by disjunction and negation ¬(¬ p∨ q) ∨ (¬r ∨ p)

2. Push negation inwards by De Morgan’s laws and involution (¬¬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))

5. and by commutative and absorption laws

p∨¬r

5. Predicates and quantifiers. Bound and free variables.

- What is Predicates?

Predicate is propositional function A propositional function is a generalization of proposition: its argument stands for en element from its domain; its value is T or F depending on the property of its argument(s).

- Quantifier?

- The universal quantification of P (x ) is the statement ”P (x ) for all values of x in the domain U.” Example: Let P (x ) be the statement ”x + 1 > x” and domain is Z. Then the quantification ∀xP (x ) is true

- The existential quantification of P (x ) is the statement ”There exists an element x in the domain U such that P (x ).”

Example: Let P (x ) be the statement ”x > 3” and domain is R. Then the quantification ∃xP (x ) is true.

• Quantifiers as conjunctions and/or disjunctions

If the domain is finite then universal/existential quantifiers can b e expressed by conjunctions/disjunctions.

If the domain U = {1 , 2 , 3 , 4}, then I ∀xP ( x ) = P (1) ∧ P(2) ∧ P(3) ∧ P(4), and I ∃xP(x) = P(1) ∨ P(2) ∨ P(3) ∨ P(4).

• The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus

-What is bound and free Variables?

Variables in the scope of some quantifier are called bound variables. All other variables in the expression are called free variables.

Example: In the statement ∃x (x + y = 1), the variable x is bound, but the variable y is free; In the statement ∃x(P(x) ∧ Q(x)) ∨ ∀xR(x), all variables are bound

6. Logical equivalences for quantifiers.

- Statements involving predicates and quantifiers are logically equivalent . if and only if they have the same truth value

- We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent Example : ∀x .¬¬ S ( x ) ≡ ∀ x . S ( x )

De Morgan’s law for quantifiers De Morgan's laws are a pair of transformation rules relating the set operators "union" and "intersection" in terms of each other by means of negation.