Logic and Foundations Assignment
Question One
The truth table
| P | Q | P Q | Q P | (P Q) P |
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Counterexamples for P and Q are:
P: T, T, F, and F
Q: T, F, T, and F
Claim: ((P Q) P) P
Proof:
1 (1) P Q A
2 (2) Q R A
3 (3) P A
1, 3 (4) Q 1, 3 MP
1, 2, 3 (5) P 2, 4 MP
1, 2 (6) P Q 3, 5 CP
Claim: ~ (P Q) ˫ P ^ ~ Q
Proof:
1 (1) P Q A
2 (2) Q P A
1, 2 (3) P A
2, 1 (4) Q 1, 2 MP
1 (5) ~ (P Q) ˫ P ^ ~ Q 2, 4 CP
Claim: ˫ ((P Q) P) P
Proof:
1 (1) ((P Q) P) P A
2 (2) P A
3 (3) Q A
1, 3 (4) P (Q P) 1, 3 MP
1, 3, 4 (5) P Q 2, 4 MP
1, 2, 3 (6) Q P 4, 6 CP
1, 2 (7) P (Q P) 4, 7 CP
1 (8) ˫ ((P Q) P) P 1, 8 CP
Question Two
Claim: (ⱴx) (F (x) v G (x)) H (x)), (Ǝx) ~ H (x) ˫ (Ǝx) ~ F (x)
Proof:
1 (1) (ⱴx) {(F(x) v G(x)) H(x)} A
2 (2) (Ǝx) ~ H(x) A
3 (3) F (a) A
1 (4) (F (a) v G (a)) H (a) 1 ⱴ E
2 (5) ~ H (a) 2 ⱴ E
1, 2 (6) ~ (F (a) v G (a)) 4, 5 MT
3 (7) F (a) v G (a) 3 v I
1, 2, 3 (8) (F (a) v G (a)) ^ ~ (F (a) v G (a)) 6, 7 ^ I
1, 2 (9 ~ F (a) 3, 8 RAA
1, 2 (10) (ⱴx) ~ F(x) 9 ⱴ I
Claim: (ⱴx) (F (x) G (x)) ˫ ((Ǝx) ~ G (x)) ((Ǝx) ~ F (x))
Proof:
Proof:
1 (1) (ⱴx) (F(x) ^ G(x)) A
1 (2) (Ǝx) ^ G (a) 1 ^ E
1 (3) F (a) 2 ⱴ E
1 (4) (8x) G(x) 1 ^ E
1 (5) G (a) 4 ⱴ I
1 (6) F (a) ^ Ǝ (a) 3, 5 ^ I
1 (7) (ⱴx) (F(x) ^ G(x)) 4, 6 ⱴ I
Claim: (ⱴx) (F (x) ~ G (x)) ˫ ~ (Ǝx) (F (x) ^ G (x))
Proof:
1 (1) (ⱴx) {F(x) G(x)} A
2 (2) (Ǝx) F(x) A
1 (3) F (a) G (a) 1 8 E
2 (4) F (a) 2 8 E
1, 2 (5) G (a) 3, 4 MP
1, 2 (6) (Ǝx) G (x) 5 8 I
1 (7) (ⱴx) F(x) (Ǝx) G (x) 2, 6 CP
Claim: (Ǝx) {F (x) ^ (ⱴy) G (y) K (x, y))},
(ⱴx) {F (x) (ⱴy) (H (y) ~ K (x, y))} ˫ (ⱴx) (G (x) ~ H (x)}
Proof:
1 (1) (Ǝx) (G(x) K (x) ^ ~ H(x)) A
2 (2) (ⱴx) (G(x) F(x)) A
3 (3) G (a) ^ ~ H (a) A
1 (4) G (a) K (a) 1 8 E
3 (5) G (a) 3 ^ E
1, 3 (6) H (a) 4, 5 MP
3 (7) F (a) 3 ^ E
1, 3 (8) F (a) ^ ~ H (a) 6, 7 ^ I
1, 3 (9) (Kx) (F(x) ^ ~ H(x)) 8 9 I
1, 2 (10) (Ǝx) (F(x) ^ ~ H(x)) 2, 3, 9 9 E
Claim: (Ǝx) (Ǝy) (ⱴz) L (x, y, z) ˫ (ⱴz) (Ǝy) (Ǝx) L (x, y, z)
Proof:
1 (1) (Ǝx) ⱴ(x) v (Ǝx) L (x) A
2 (2) (Ǝx) L(x) A
3 (3) L (a) A
3 (4) L (a) v ⱴ (a) 3 v I
3 (5) (Ǝx) (ⱴ(x) v L(x)) 4 Ǝ I
2 (6) (Ǝx)(ⱴ(x) v L(x)) 2, 3, 5 Ǝ E
7 (7) (Ǝx) L(x) A
8 (8) L (a) A
8 (9) ⱴ (a) v L (a) 8 v I
8 (10) (Ǝx) (ⱴ(x) v L(x)) 9 Ǝ I
7 (11) (Ǝx) (ⱴ(x) v L(x)) 7, 8, 10 Ǝ E
1 (12) (Ǝx) (ⱴ(x) v L(x)) 1, 2, 6, 7, 11 v E
Question Three
A critical evaluation of all the steps shows that step number 7 is the one which is faulty. This is attributable to the fact that this step should be concerned with two variables such as (Ǝ) y and (Q) y, but it makes reference to step 3 which is purely concerned with variable P (a). As a result of this, step 7 becomes faulty and it cannot facilitate successful completion of the solution to the question of interest.
Let U = {1, 2}, a two element universe of discourse with distinct objects 1 and 2.
Suppose that F(x) means “x = 1” and G(x) means “x = 2”. Then
(Ǝx) (P(x) Q (x)) ˫ ((Ǝx) (P(x)) (Ǝ (y) Q (y)) is not true
Because, for each x ϵ U, either x = 1 or x = 2. However,
Ǝ (2) is false,
So that
(Px) Q(x) is false.
Similarly,
Q (1) is false,
So that
(Ǝx) P(x) is false.
Hence
(Ǝx) P (x) V (ϵx) Q(x) is false,
Whilst
(Ǝx)P(x)) (Ǝx) Q(x) is trivially true.
Note further that
P (1) is true
So that
P (1)) Q(1) is false,
So that
(Ǝx)(P(x)) Q(x)) is false.
Hence the sequents:
(Ǝx)P(x)) (Ǝx) Q(x) ˫ (Ǝx)(F(x) ) Q(x))
And
(Ǝx)(P(x) V Q(x)) ˫ (Ǝx) F(x) V (Ǝx) Q(x)
Cannot be proved using the rules of Predicate Calculus, for otherwise, in each case, you would have a false conclusion following from a true premise, contradicting Soundness.
Question Four
Let U = W*, and for all x, y ϵ W*, interpret W1(x, y) to mean x < y. certainly, for each x ϵ W*, x 6< x, so that W1 holds in W2. Furthermore, < is transitive,
That is, for all x, y, z ϵ W*,
x < y < z) x < z,
So that W2 holds in W1. Finally, for all x, y ϵ W*, we can take z = max{x, y} + 1, and it is certainly true that,
x < z and y < z,
So that W* holds in U. This proves that U serves as a model for W1, W2, and W*.
Question Five
W2 = P ˫ P2 ˫ P4
W3 = P V P3 P^ P2 ˫ P4
W4 = P ˫ P2 ~ P3 V P4
This implies that h: x 7→ x + 1 for all x 2 N and can also be expressed as g: x 7→ x − 1 for all x 2 Z+
Thus, Wn is shown to have 4n-3 symbols.
References
Barwise, J. (1977). Handbook of mathematical logic: logic and the foundations of mathematics. Amsterdam: North-Holland Publishing Co.
Enderton, H. B. (1972). A mathematical introduction to logic. New York, NY: Academic Press.
Last Completed Projects
| topic title | academic level | Writer | delivered |
|---|