Please i need emergency help with these 4 tasks. I had to do 20 of them, i have completed 16 and i have no idea how to do these 4. These are the tasks in topic :
1. Prove the following, using Natural Deduction. (This question is testing your ability to use Natural Deduction, therefore it is important to show every step of your work.) Prove T from the following premises (1)-(4).
(1) ¬P ∧ Q
(2) R → P
(3) ¬R → S
(4) S → T
2.Prove the following using Tableaux: (((¬P ∧ Q) ∧ (R → P)) ∧ ((¬R → S) ∧ (S → T))) → T. (This question is testing your ability to use Tableau proofs, therefore it is important to show every step of your work.)
3. {¬, ∧} is a functionally complete set of propositional logic connectives. Use this information to prove that the following set is functionally complete as well: {N}, where ϕNψ is defined to be true if ϕ and ψ are both false, and false otherwise. (Accordingly, one might pronounce N as ”neither”.)
4. Consider the formal definition of a Regular Expression (RE) in the lecture slides on Regular Expressions (using rules (i), (ii) and (iii) only, so no abbreviation rules or added constructs). Consider the following proposition: Every RE except ”{}” denotes a nonempty set of strings. Now consider the following real or purported proof (by formula induction) of this proposition:
For any RE ϕ, let P(ϕ) say that ϕ is {} or denotes a nonempty set of strings.
Base step: for the base step, we need to prove that (1) P({}), (2) P(λ), and (3) P(t) (for any symbol t). These 3 proofs go as follows:
(1) this is true by definition of P (which contains {} as its first disjunct)
(2) this is true because λ denotes {λ}, which is a nonempty set of strings
(3) this is true because t denotes {t}, which is a nonempty set of strings
So, the proposition holds for all ”base” formulas. How about more complex formulas?
Induction step: Assume P holds for the REs r and s. From this assumption we need to prove that P holds for (1) (r + s), (2) (rs), and (3) (r∗). These 3 proofs go as follows: (.......)
Please discuss: Can this proof be made correct? If so, then complete the proof (where the dots are). If not, then explain precisely where the plan of the proof is flawed. Is the proposition true? If not then provide a counterexample.
If you can provide some explanation as well i will greatly appreciate it.
1. Prove the following, using Natural Deduction. (This question is testing your ability to use Natural Deduction, therefore it is important to show every step of your work.) Prove T from the following premises (1)-(4).
(1) ¬P ∧ Q
(2) R → P
(3) ¬R → S
(4) S → T
2.Prove the following using Tableaux: (((¬P ∧ Q) ∧ (R → P)) ∧ ((¬R → S) ∧ (S → T))) → T. (This question is testing your ability to use Tableau proofs, therefore it is important to show every step of your work.)
3. {¬, ∧} is a functionally complete set of propositional logic connectives. Use this information to prove that the following set is functionally complete as well: {N}, where ϕNψ is defined to be true if ϕ and ψ are both false, and false otherwise. (Accordingly, one might pronounce N as ”neither”.)
4. Consider the formal definition of a Regular Expression (RE) in the lecture slides on Regular Expressions (using rules (i), (ii) and (iii) only, so no abbreviation rules or added constructs). Consider the following proposition: Every RE except ”{}” denotes a nonempty set of strings. Now consider the following real or purported proof (by formula induction) of this proposition:
For any RE ϕ, let P(ϕ) say that ϕ is {} or denotes a nonempty set of strings.
Base step: for the base step, we need to prove that (1) P({}), (2) P(λ), and (3) P(t) (for any symbol t). These 3 proofs go as follows:
(1) this is true by definition of P (which contains {} as its first disjunct)
(2) this is true because λ denotes {λ}, which is a nonempty set of strings
(3) this is true because t denotes {t}, which is a nonempty set of strings
So, the proposition holds for all ”base” formulas. How about more complex formulas?
Induction step: Assume P holds for the REs r and s. From this assumption we need to prove that P holds for (1) (r + s), (2) (rs), and (3) (r∗). These 3 proofs go as follows: (.......)
Please discuss: Can this proof be made correct? If so, then complete the proof (where the dots are). If not, then explain precisely where the plan of the proof is flawed. Is the proposition true? If not then provide a counterexample.
If you can provide some explanation as well i will greatly appreciate it.
Last edited by a moderator:
