Propositional Logic Questions 18-23 PDF

Preview

Summary

Textbook questions- These are my thoughts and perspectives before course lectures begin...

Description

Question 18 Let s be the statement whose truth table is given below.

(a) Express the statement s in terms of p, q and r in such a way that only negation (¬) and the logical connectives ∨ and ∧ are used. Row 1: ¬p ∧ ¬q ∧ ¬r Row 2: p ∧ q ∧ r Row 3: p ∨ q ∨ r Row 4: p ∧ q ∧ r Row 5: p ∧ q ∧ r Row 6: p ∧ q ∧ r Row 7: p ∧ q ∨ r Row 8: ¬p ∧ ¬q ∧ ¬r Find an equivalent formulation of s that uses only ¬ and ∨. Row 1: ¬p ∨ q ∨ r Row 2: p ∨ q ∨ ¬r Row 3: p ∨ q ∨ r

Row 4: p ∨ ¬q ∨ ¬r Row 5: ¬p ∨ q ∨ r Row 6: ¬p ∨ q ∨ ¬r Row 7: p ∨ q ∨ r Row 8: ¬p ∨ ¬q ∨ ¬r

(c) Find an equivalent formulation of s that uses only ¬ and ∧. Row 1: ¬p ∧ ¬q ∧ ¬r Row 2: p ∧ q ∧ r Row 3: ¬p ∧ q ∧ ¬r Row 4: p ∧ q ∧ r Row 5: p ∧ q ∧ r Row 6: p ∧ q ∧ r Row 7: p ∧ q ∧ ¬r Row 8: ¬p ∧ ¬q ∧ ¬r

Question 19 Define the logical connective “nand” (not and) by

p

q

¬p

p∧q

0

0

1

0∧0

0

1

1

1

0

1

1

0

0

p∨q

p→q

p↔q

0∨0

0→0

0↔0

0

0

1

1

0∧1

0∨1

0→1

0↔1

0

1

1

0

1∧0

1∨0

1→0

1↔0

0

1

0

0

1∧1

1∨1

1→1

1↔ 1

1

1

1

1

¬ (p ∧ q) ⇔ ¬p ∨ ¬q De Morgan’s laws Negation of conjunction: -It will be false if p ∧ q both are true otherwise true -the disjunction of the negations

(a) Find a representation of each of the following statements using only the logical connective nand. i. ii. iii. iv.

¬p = p nand p p ∧ q = ¬ (p nand q) = ¬ (p ∧ p) nand (q ∧ q) p ∨ q = ¬ (¬p ∧ ¬q) = ¬ p nand ¬q = (p nand p) nand (q nand q) p → q = ¬p ∨ q = (p nand p) ∨ (q ∧ q)

v.

p ↔ q = (p → q) ∧ (q → p) = ¬p ∨ q ∧ ¬q ∨ p = [(p nand p) ∨ (q ∧ q)] ∧ [(q nand q) ∨ (p ∧ p)]

(b) Explain why every statement has a representation using only the logical connective nand. The theorem that every statement is logically equivalent to one that is in disjunctive normal form. It transpires that any proposition can be expressed (in a possibly complicated way) using only “nand”. The same thing applies to “nor”, where “p nor q” is the statement.

Question 20 Repeat question 19 using the logical connective “nor” (not or) defined by p

q ⇔ ¬ (p ∨ q).

(a) Find a representation of each of the following statements using only the logical connective nor. i. ii. iii. iv. v.

¬p p∧q p∨q p→q p↔q

Question 21 Referring to questions 19 and 20, prove that ¬ (p

q) ⇔ ¬p

¬q.

DeMorgan’s law stipulates that ¬ (p ∧ q) ⇔ ¬p ∨ ¬q DeMorgan’s law stipulates that ¬ (p ∨ q) ⇔ ¬p ∧ ¬q Negation of disjunction: -Since two things are both false, it is also false that either of them is true -conjunction of the negations Guess and prove a similar logical equivalence for ¬ (p

Question 22

q).

(a) Argue that “logically implies” has the property (called transitivity) that if a, b and c are statements such that a ⇒ b and b ⇒ c, then a ⇒ c. The laws of inference, in particular hypothetical syllogism infer transitivity. A truth table can, in principle, be used to show an argument is valid.

a

b

c

a⇒b

b⇒c

a⇒c

0

0

0

0⇒0

0⇒0

0⇒0

0

0

1

0⇒0

0⇒1

0⇒1

0

1

0

0⇒1

1⇒0

0⇒0

1

0

0

1⇒0

0⇒0

1⇒0

0

1

1

0⇒1

1⇒1

0⇒1

1

1

0

1⇒1

1⇒0

1⇒0

1

1

1

1⇒1

1⇒1

1⇒1

A better way is to give a proof: a chain of logical equivalences and implications involving the premises

(b) Suppose a, b, c and d are statements such that a ⇒ b, b ⇒ c, c ⇒ d, and d ⇒ a. Argue that any two of these statements are logically equivalent. A truth table can, in principle, be used to show an argument is valid.

a

b

c

d

a⇒b

b⇒c

c⇒d

d⇒a

0

0

0

0

0⇒0

0⇒0

0⇒0

0⇒0

0

0

1

0

0⇒0

0⇒1

1⇒0

0⇒0

0

1

0

0

0⇒1

1⇒0

0⇒0

0⇒0

1

0

0

0

1⇒0

0⇒0

0⇒0

0⇒1

0

1

1

0

0⇒1

1⇒1

1⇒0

0⇒0

1

1

0

0

1⇒1

1⇒0

0⇒0

0⇒1

1

1

1

0

1⇒1

1⇒1

1⇒0

0⇒1

0

0

0

1

0⇒0

0⇒0

0⇒1

1⇒0

0

0

1

1

0⇒0

0⇒1

1⇒1

1⇒0

0

1

1

1

0⇒1

1⇒1

1⇒1

1⇒0

1

1

1

1

1⇒1

1⇒1

1⇒1

1⇒1

A better way is to give a proof: a chain of logical equivalences and implications involving the premises

Question 23 Determine whether each statement is true or false, and briefly explain your reasoning.

(a) If an argument is valid then it is possible the conclusion to be false when all premises are true. (b) If the premises can’t all be true, then the argument is valid. (c) If p ⇔ q and q ⇔ r, then p ⇔ r....