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