by the implication law (the first law in Table 7.) ≡q ∨ (¬p) by commutative Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology. sol: (p ∨ q) ...
5. Prove [(p → q) ∧ (q → r)] ⇒ (p → r) using a truth table. Exercise 2.6.6.
Prove that: [(p → q) ∧ (q → r)] → [p → r] is a tautology. By using truth table. By using logic equivalence laws. We will show these examples in class. c
Similarly (q ∨ r) ∧ p ⇔ (q ∧ p) ∨ (r ∧ p). The Laws of Logic can be used in several other ways. One of them is to prove that a statement is a tautology
if p then q; and if r then s; but either not q or not s; therefore either not p or not r. Simplification. (p ∧ q). ∴ p p and q are true; therefore p is
This rule plays an important role in AI systems. Intuitively it means: if P implies R and ¬ P implies Q (why? Where do we get these implications?)
(p^q) ^r = p ^ (q ^ r) EXAMPLE 6*. Show that (p ^ q) → (p ≤ q) is a tautology. Solution: To show that this statement is a tautology we will use logical ...
Jan 6 2020 ≡ ¬p ∨ q. (Using that (¬p ∨ p) is a tautology). D. Exercise 9. Use the laws of logic to simplify (s ∨ (p ∧ r ∧ s)) ∧ (p ∨ (p ∧ q ∧ ¬r) ...
The argument is valid since ((p → q) ∧ p) → q is a tautology. CSI2101 A real number r is rational if there exists integers p and q with q = 0 such.
Since [(p ? q) ? (q ? r)] ? (p ? r) is always T it is a tautology. (0 points) (c) by the implication law (the first law in Table 7.) ?q ? (¬p).
q ? (p ? r) following propositional formulae are tautologies by showing they are equivalent ... simplify it using axioms and laws of boolean algebra.
Prove that: [(p ? q) ? (q ? r)] ? [p ? r] is a tautology. By using truth table. By using logic equivalence laws. We will show these examples in class. c
Example 2.1.2. p ? ¬p. Definition 2.1.3. A contingency is a proposition that is neither a tautology nor a contradiction. Example 2.1.3. p ? q ? ¬r.
) Show that ( p ? q ) ? ( p ? r ) and p ? ( q ? r ) are logically equivalent ? Solution: Page 22. Math 151 Discrete Mathematics ( Propositional Logic ). By
(4 points) Show that (P ? (Q ? R)) ? ((P ?Q) ? R) is tautology using logical (4 points) Validate the following argument by rules of inference ...
The rules of logic specify the meaning of mathematical statement. (equivalent). Example p ? q. ? r. ? p ? (q ? r). Pattarawit Polpinit. Lecture 5 ...
d) q ? p: If the votes are counted then the election is decided. e) ¬q ? ¬p: The 1.3.30 Show that (p ? q) ? (¬p ? r) ? (q ? r) is a tautology.
p ? ¬q. Using the same reasoning or by negating the negation
(2pt each) Write these propositions using r s
Prove: If p ?r and q ?¬r then p ?q ?s Equivalently prove: (p ?r) ?(q ?¬r ) ?(p ?q ?s) 1 p ?r Premise 2 ¬p ?r 1 Implication 3 q ?¬r Premise 4 ¬q ?¬r 3 Implication 5 ¬p ?¬q 2 4 Resolution 6 ¬(p ?q ) 5 DeMorgan
p q r q p r ? q aka Disjunction Elimination Corresponding Tautology: ((p q) ? (r q) ? (p r )) q Example: Let p be “I will study discrete math ” Let q be “I will study Computer Science ” Let r be “I will study databases ” “If I will study discrete math then I will study Computer Science ”
Tautologies Contradictions and Contingencies A tautology is a compound proposition which is always true A contradiction is a compound proposition which is always false A contingency is a compound proposition which is neither a tautology nor a contradiction Logical Equivalences
Example 2 1 3 p_q!:r Discussion One of the important techniques used in proving theorems is to replace or sub-stitute one proposition by another one that is equivalent to it In this section we will list some of the basic propositional equivalences and show how they can be used to prove other equivalences
(P ? (Q ? R)) ? (P ?Q ? R) is a tautology A sentence of the language of propositional logic is a tautology (logically true) if and only if the main column has T in every line of the truth value (that is if and only if the sentence is true in any L Ô-structure)
tation they lead to the same value Hint: use truth table to show the equivalence P R Q (P ? R) Q ? R (P ? R)? Q ? R (P ? Q) ? R) We can prove
A sentence of the language of propositional logic is a tautology (logically true) if and only if the main column has T in every line of the truth value (that is, if and only if the sentence is true in any L. Ô-structure). Ø(P ?(Q ?R)) ?(P ? Q ?R) As it stands, the sentence (P ? (Q ? R)) ? (P ?Q ? R) is merely in abbreviated form.
1.3 Propositional Equivalences Tautologies, Contradictions, and Contingencies A tautology is a compound proposition which is always true. A contradiction is a compound proposition which is always false. A contingency is a compound proposition which is neither a tautology nor a contradiction.
?a tautology, or ?an axiom/law of the domain (e.g., 1+3=4 orx> +1 ) ?justified by definition, or ?logically equivalent to orimpliedby one or more propositions pk
?Prove: If p?rand ¬r, then q?¬p ?Equivalently, prove: (p?r) ?( ¬r ) ?( q?¬p) 1. p?r Premise 2. ¬r Premise 3. ¬p1, 2, modus tollens