CS 512, Spring 2017, Handout 08 - BU
CS 512, Spring 2017, Handout 08 Do You Believe de Morgan's Laws?
Assaf Kfoury
January 31, 2017
Assaf Kfoury, CS 512, Spring 2017, Handout 08
page 1 of 22
Do You Believe de Morgan's Laws Are Tautologies?
Assaf Kfoury, CS 512, Spring 2017, Handout 08
page 2 of 22
Do You Believe de Morgan's Laws Are Tautologies?
Of course you believe they are! But now, for each, choose a most efficient procedure to confirm it!
Assaf Kfoury, CS 512, Spring 2017, Handout 08
page 3 of 22
Do You Believe de Morgan's Laws Are Tautologies?
Of course you believe they are! But now, for each, choose a most efficient procedure to confirm it! de Morgan's laws can be expressed in four propositional WFF's:
1. ?(p q) (?p ?q)
2. (?p ?q) ?(p q)
3. ?(p q) (?p ?q)
4. (?p ?q) ?(p q)
or, in the form of four valid/formally deducible sequents:
1. ?(p q) (?p ?q)
2. (?p ?q) ?(p q)
3. ?(p q) (?p ?q)
4. (?p ?q) ?(p q)
Assaf Kfoury, CS 512, Spring 2017, Handout 08
page 4 of 22
Available methods
Already discussed: Natural-deduction formal proofs? Truth-tables? Yet to be discussed: Analytic tableaux? Resolution? DP or DPLL procedures?
Assaf Kfoury, CS 512, Spring 2017, Handout 08
page 5 of 22
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.