MATH 160A FALL 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 160A
FALL 2022
Homework – week 1
1. [ACS] Using the “logical” meaning of if–then, and assuming that statements such as “pigs can fly” are given their usual real-world true/false values, determine whether the following sentences are true or false.
(a) If pigs can fly then the sun rises in the east.
(b) If the sun rises in the east then pigs can fly.
(c) If the sun rises in the west then oysters have feet.
(d) If the sea is wet then a dog has more legs than a parrot.
(e) If a dog has more legs than a parrot, then if the sun rises in the west then pigs can fly.
2. In this question, let p1 , p2 , p3 , p4 , p5 denote the statements p1 : a pig’s house is made of straw p2 : a pig’s house is made of bricks
p3 : a wolf blows on the house
p4 : the house is hit by a 100-year storm
p5 : the house falls down.
For each of the following sentences (considered individually), translate it into a single propositional formula using p1 , p2 , p3 , p4 , p5 and any of the logic symbols ^, V, -, → , e→ , 1 you want.
(a) If the house is made of straw, then if a wolf blows on the house it will fall down. (b) The pig’s house is made of straw or bricks, but not both.
(c) If a wolf blows on the house, it will fall down unless it is made of bricks.
(d) If a wolf blows on the house, it will fall not fall down if it is made of bricks.
(e) If the pig’s house is made of bricks, then it will fall down if it is hit by a hundred-year storm but
not if it is blown on by a wolf.
3. For each sentence (i)– (v) in Q2, translate it into a single propositional formula using p1 , . . . , p5 and only the logic symbols → , 1 (i.e., a proposition in the formal language L(P)).
4. Find a propositional formula in L(P) (i.e., only using → and 1) equivalent to the informal state- ment “p1 , p2 , p3 are either all true or all false” .
5. [ACS] For each of the following propositional formulae, determine with proof whether or not it is a tautology.
(a) ((p1 → (p2 → p3 )) → (p2 → (p1 → p3 ))).
(b) ((p1 → 1) → p2 ) → p1 .
(c) ((p1 → (p2 → 1)) → 1) → p2 .
(d) ((p1 ^ p2 ) ^ (p1 ^ p3 )) → (p2 ^ p3 ).
(e) ((p1 → (-p2 )) → (p2 → (-p1 ))).
6. [ACS] Which of the following hold? Justify your answers.
(a) {p1 } |= (p2 → p3 ).
(b) {p1 } |= (p2 → p1 ).
(c) {p1 , p2 } |= ((p1 → (p2 → 1)) → 1).
(d) {1} |= p7 .
(e) {(p1 → p2 ), (p3 → (p2 → 1))} |= (p1 → (-p3 )).
7. Suppose S, T are two sets of propositions in L(P). We say they are tautologically equivalent if S |= t for every t e T and T |= s for every s e S .
(a) If S is finite, show that there is a single proposition t e L(P) such that S and {t} are tautologically
equivalent.
(b) Give an example of an infinite set S of propositions that is not tautologically equivalent to any
finite set.
8. Give an example of propositions p, q e L(P) such that ╱(p → q) → (-(q → p))、is a tautology.
2022-10-07