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.

7. Propositional calculus PC. Derivation in classical logic.

The standard logical constants of PC = ¬ = not & = and v = or → = if…, then… ↔ = if and only if (iff)

8. Semantics of predicate calculus. Validity and satisfiability of predicate statements.

-Semantics of predicate calculus In the semantics of propositional logic, we assigned a truth value to each atom. In predicate logic, the smallest unit to which we can assign a truth value is a predicate P(t 1, t2, . . . , tn) applied to terms.

But we cannot arbitrarily assign a truth value, as we did for propositional atoms. There needs to be some consistency. We need to assign values to variables in appropriate contexts, and meanings to functions and predicates. Intuitively, this is straightforward, but we must define such things precisely in order to ensure consistency of interpretation.

2 Example In Module 5, we considered the formula ∀x(P(x) ∧ ¬Q(x) → R(x)) . 

Our interpretation of this statement was, “Every student who took CS245, but did not pass CS245, failed CS245.” Under this interpretation, x ranges over all students (say, at UW). So, since x is a placeholder for a term, terms t denote UW students. P, Q, and R, then are properties of students. We can think of them as B-valued functions on UW students:

P(x) = “x took CS245”, 

Q(x) = “x passed CS245”,

R(x) = “x failed CS245” 3

More abstractly, P, Q, and R are sets: P = {students who took CS245} Q = {students who passed CS245} R = {students who failed CS245} Then P(x) is shorthand for x ∈ P, and similarly for Q and R.

-An assertion in predicate calculus is logically valid (or simply valid) if it is true in every interpretation, that is iff it is true +for all domains +for every propositional functions substituted for the predicates in the assertion

Example: ∀x .( P( x) ∨¬ P( x))

- 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

Example: ∀x .∃ y . P ( x , y ) is satisfiable

9. Sequent predicate calculus LK.

This section introduces the rules of the sequent calculus LK, as introduced by Gentzen in 1934.A (formal) proof in this calculus is a sequence of sequents, where each of the sequents is derivable from sequents appearing earlier in the sequence by using one of the rules below (inference rule) The following notation will be used:

10. Proof techniques. Constructive and non-constructive proofs.

”Trivial” proofs

If we know ∀x Q(x) is true, then ∀x (P(x) → Q(x)) is true as well For all x ∈ N, if x is even, then x = x

”Vacuous” proof

If we know ∀x ¬P(x) is true, then ∀x P(x) → Q(x) is true as well. For all x ∈ N, if x < x, then x is even

Contraposition

Let u ∈ U. Prove that ¬Q(u) → ¬P(u). By equivalence of a statement with it contrapositive derive that P(u) → Q(u). Finally by universal generalization we can conclude that

∀x (P(x) → Q(x)).

For all integers x and y, if x + y is even, then x and y have the same parity

Proof by contradiction

To prove that P is true, we assume that it is not. That is we assume ¬P, and then prove both

R and ¬R. But for any proposition R, R ∧ ¬R ≡ F. So we have shown that ¬P → F. The only way this implication can be true is if ¬P is false, i.e. P is true. √2 is irrational.

Proof by cases A proof by cases must cover all possible cases that arise in a theorem. We illustrate proof by cases with a couple of examples. In each example, you should check that all possible cases are covered.

Constructive and non-constructive proofs

Constructive proof of ∃ x P ( x )

Find an explicit value of u ∈ U, for which P(u) is true There exists a positive integer that can b e written as the sum of cubes of positive integers in two different ways

Example: Pr of. 1729 is such a number since 1729 = 10 3 + 9 3 = 12 3 + 1 3.

non-constructive proofs

In a non-constructive existence pro of, we prove that there must exist a u ∈ U exists which

makes P(u) without actually finding this u.

Example: There exist some irrational numb ers x and y such that x y is rational.

Proof by counter-examples

Recall ∃x ¬P(x) ≡ ¬∀x P(x). To establish that ¬∀x P(x) is true (or is false) find a u ∈ U such that ¬P(u) is true or

P(u) is false.

Example: Every positive integer is the sum of the squares of 3 integers