2. Propositional Equivalences 2.1. Tautology/Contradiction
Show that (p → q) ∧ (q → p) is logically equivalent to p ↔ q. Solution 1. Show the truth values of both propositions are identical. Truth Table: p q p
Propositional Logic Discrete Mathematics
Prove that: [¬ p ∧ (p ∨ q)] → q is a tautology. By using truth table. By using logic equivalence laws. Example: (Page 35 problem 10 (b).
Chapter 1 Logic
Observe that the pairs of statements in question have the same truth value given any combination of possible truth values of p and q. p q ¬p ¬q p ∧ q ¬(p ∧ q)
MA0301 ELEMENTARY DISCRETE MATHEMATICS NTNU
6 янв. 2020 г. Use a truth table to show that ¬(p ⇒ q) is logically equivalent to p ∧ ¬q. Solution. The truth table is. p q ¬q p ⇒ q ¬(p ⇒ q) p ∧ ¬q.
L.4 Logical Equivalence L.5 Laws of Logical Equivalence
So we could just do a single truth table for P ↔ Q to show that P Q are logically Notation: if P
Homework #1 Chapter 2
P ↔ Q is defined as being equivalent to. (P →. ∧. Q) (Q → P). Based on this definition show logical equivalence of. P ↔ Q and P ∨Q → P ∧ Q: P Q P
Untitled
Show that (p V (~p ^ q)) and ¬p ^ ¬q are logically equivalent. Solution: We could use a truth table to show that these compound propositions are equivalent.
Exam 1: Solutions
(b) show that (p ∧ q) → r and (p → r) ∧ (q → r) are not logically equivalent. Solution. (a) We have. p q p ↔ q p ∧ q ¬p ¬q ¬p∧¬q (p∧q)
Discussion 4: Solutions
26 янв. 2022 г. p q p ↓ q. T T. F. T F. F. F T. F. F F. T b) Show that p ↓ q is logically equivalent to ¬(p ∨ q). p q p ↓ q p ∨ q ¬(p ∨ q). T T. F. T. F.
Section 1.2 selected answers Math 114 Discrete Mathematics
Show that ¬(p ⊕ q) and p ←→ q are logically equiva- lent. This is an important logical equivalence and well worth memorizing. The proof is easy by a truth
2. Propositional Equivalences 2.1. Tautology/Contradiction
The proposition p ? ¬(p ? q) is also a tautology as the following the truth table Show that (p ? q) ? (q ? p) is logically equivalent to p ? q.
Propositional Logic Discrete Mathematics
Prove that: [¬ p ? (p ? q)] ? q is a tautology. By using truth table. By using logic equivalence laws. Example: (Page 35 problem 10 (b).
Chapter 1. The Foundations: Logic and Proofs 1.4 Logical
Two compound propositions p and q
Section 1.2 selected answers Math 114 Discrete Mathematics
columns for ¬(p ? q) and ¬p ? ¬q are identical therefore they're logically equivalent. 12. Show that each implication in Exercise 10 is a tautol-.
(1) Propositional Logic
Math 151 Discrete Mathematics ( Propositional Logic ). By: Malek Zein AL-Abidin. EXAMPLE 2 Show that ?(p ? q) and ?p ??q are logically equivalent.
Week 3-4
The Biconditional Implication of statements p and q is the statement. (p ? q)?(q ? p). Since this compound sentence is important we introduce a new symbol p
Chapter 1 Logic
LOGIC. The conjunction of p and q (read: p and q) is the statement p ? q Formally two statements s1 and s2 are logically equivalent if s1 ? s2 is a.
CS 2336 Discrete Mathematics
“p and q.” The truth value of p ? q is true if both p logical operators is by using a truth table ... Ex: Show that p ? q and ¬ p ? q are equivalent.
Exam 1 solutions.pdf
Using truth tables. (a) show that p ? q and (p ? q) ? (¬p ? ¬q) are logically equivalent. (b) show that (p ? q) ? r and (p ? r) ? (q ? r) are not
Homework #1 Chapter 2
(P?Q) ? (Q?P). Based on this definition show that P ? Q is logically equivalent to. (P?Q) ? (P?Q) a) By using truth table. The logical operator
Are p q and q p logically equivalent?
By looking at the truth table for the two compound propositions p ? q and ¬q ? ¬p, we can conclude that they are logically equivalent because they have the same truth values (check the columns corresponding to the two compound propositions) Use truth tables to verify these equivalences ( Ex.1 pp 34 from the textbook)
Is if true if p and Q have the same truth values?
It is true if both p and q have the same truth values and is false if p and q have opposite truth values. The words if and only if are sometimes abbreviated iff. The biconditional has the following truth table: Truth Table for p ? q p q p?q T T T T F F F T F F F T In order of operations ? is coequal with ?.
What is the set corresponding to the proposition (p ? q)?
The set corresponding to the proposition (p ? q) is (PQ ? (PcQc)) . If P = Q, then so in that case, (p ? q) is always true. A proposition p is a statement that can be true (T) or false (F). Logical operations turn propositions into other propositions; examples include !, |, &, ?, ?. They operate as shown in the following table:
How to define p q as a statement?
To de?ne p ? q as a statement, therefore, we must specify the truth values for p ? q as we speci?ed truth values for p ? q and for p ? q. As is the case with the other connectives, the formal de?nition of truth values for ? (if-then) is based on its everyday, intuitive meaning. Consider an example.
2. PROPOSITIONAL EQUIVALENCES 33
2. Propositional Equivalences
2.1. Tautology/Contradiction/Contingency.
Definition2.1.1.Atautologyis a proposition that is always true.Example2.1.1.p_ :p
Definition2.1.2.Acontradictionis a proposition that is always false.Example2.1.2.p^ :p
Definition2.1.3.Acontingencyis a proposition that is neither a tautology nor a contradiction.Example2.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. Let us look at the classic example of a tautology,p_ :p. The truth table p:pp_ :pTFT FTT shows thatp_ :pis true no matter the truth value ofp. [Side Note.This tautology, called thelaw of excluded middle, is a direct consequence of our basic assumption that a proposition is a statement that is either true or false. Thus, the logic we will discuss here, so-called Aristotelian logic, might be described as a \2-valued" logic, and it is the logical basis for most of the theory of modern mathematics, at least as it has developed in western culture. There is, however, a consistent logical system, known as constructivist, or intuitionistic, logic which does not assume the law of excluded middle. This results in a 3-valued logic in which one allows for2. PROPOSITIONAL EQUIVALENCES 34
a third possibility, namely, \other." In this system proving that a statement is \not true" is not the same as proving that it is \false," so that indirect proofs, which we shall soon discuss, would not be valid. If you are tempted to dismiss this concept, you should be aware that there are those who believe that in many ways this type of logic is much closer to the logic used in computer science than Aristotelian logic. You are encouraged to explore this idea: there is plenty of material to be found in your library or through the worldwide web.] The propositionp_ :(p^q) is also a tautology as the following the truth table illustrates. pq(p^q):(p^q)p_ :(p^q)TTTFT TFFTT FTFTT FFFTT Exercise2.1.1.Build a truth table to verify that the proposition(p$q)^(:p^q) is a contradiction.2.2. Logically Equivalent.
Definition2.2.1.Propositionsrandsarelogically equivalentif the statement r$sis a tautology. Notation:Ifrandsare logically equivalent, we write r,s:Discussion
A second notation often used to mean statementsrandsare logically equivalent isrs. You can determine whether compound propositionsrandsare logically equivalent by building a single truth table for both propositions and checking to see that they have exactly the same truth values. Notice the new symbolr,s, which is used to denote thatrandsare logically equivalent, is dened to mean the statementr$sis a tautology. In a sense the2. PROPOSITIONAL EQUIVALENCES 35
symbols$and,convey similar information when used in a sentence. However, r,sis generally used to assert that the statementr$sis, in fact, true while the statementr$salone does not imply any particular truth value. The symbol,is the preferred shorthand for \is equivalent to."2.3. Examples.
Example2.3.1.Show that(p!q)^(q!p)is logically equivalent top$q. Solution 1.Show the truth values of both propositions are identical.Truth Table:pqp!qq!p(p!q)^(q!p)p$qTTTTTT
TFFTFF
FTTFFF
FFTTTT
Solution 2.Examine every possible case in which the statement(p!q)^(q!p) may not have the same truth value asp$q Case 1. Suppose(p!q)^(q!p)is false andp$qis true. There are two possible cases where(p!q)^(q!p)is false. Namely,p!qis false orq!p is false (note that this covers the possibility both are false since we use the inclusive \or" on logic). (a) Assumep!qis false. Thenpis true andqis false. But if this is the case, thep$qis false. (b) Assumeq!pis false. Thenqis true andpis false. But if this is the case, thep$qis false. Case 2. Suppose(p!q)^(q!p)is true andp$qis false. If the latter is false, thepandqdo not have the same truth value and the there are two possible ways this may occur that we address below. (a) Assumepis true andqis false. Thenp!qis false, so the conjunction also must be false. (b) Assumepis false andqis true. Thenq!pis false, so the conjunction is also false. We exhausted all the possibilities, so the two propositions must be logically equivalent.2. PROPOSITIONAL EQUIVALENCES 36
Discussion
This example illustrates an alternative to using truth tables to establish the equiv- alence of two propositions. An alternative proof is obtained by excluding all possible ways in which the propositions may fail to be equivalent. Here is another example.Example2.3.2.Show:(p!q)is equivalent top^ :q.
Solution 1.Build a truth table containing each of the statements.pq:qp!q:(p!q)p^ :qTTFTFFTFTFTT
FTFTFF
FFTTFF
Since the truth values for:(p!q) andp^:qare exactly the same for all possible combinations of truth values ofpandq, the two propositions are equivalent. Solution 2.We consider how the two propositions couldfailto be equivalent. This can happen only if the rst is true and the second is false or vice versa.Case 1. Suppose:(p!q) is true andp^ :qis false.
:(p!q) would be true ifp!qis false. Now this only occurs ifpis true andqis false. However, ifpis true andqis false, thenp^ :qwill be true.Hence this case is not possible.
Case 2. Suppose:(p!q) is false andp^ :qis true.
p^ :qis true only ifpis true andqis false. But in this case,:(p!q) will be true. So this case is not possible either. Since it is not possible for the two propositions to have dierent truth values, they must be equivalent. Exercise2.3.1.Use a truth table to show that the propositionsp$qand:(pq) are equivalent. Exercise2.3.2.Use the method of Solution 2 in Example 2.3.2 to show that the propositionsp$qand:(pq)are equivalent.2. PROPOSITIONAL EQUIVALENCES 37
2.4. Important Logical Equivalences.The logical equivalences below are im-
portant equivalences that should be memorized.Identity Laws:p^T,p
p_F,pDomination Laws:p_T,T
p^F,FIdempotent Laws:p_p,p
p^p,pDouble Negation:(:p),p
Law:Commutative Laws:p_q,q_p
p^q,q^pAssociative Laws: (p_q)_r,p_(q_r)
(p^q)^r,p^(q^r)Distributive Laws:p_(q^r),(p_q)^(p_r)
p^(q_r),(p^q)_(p^r)De Morgan's Laws::(p^q), :p_ :q
:(p_q), :p^ :qAbsorption Laws:p^(p_q),p
p_(p^q),p2. PROPOSITIONAL EQUIVALENCES 38
Implication Law: (p!q),(:p_q)
Contrapositive Law: (p!q),(:q! :p)
Tautology:p_ :p,T
Contradiction:p^ :p,F
Equivalence: (p!q)^(q!p),(p$q)
Discussion
Study carefully what each of these equivalences is saying. With the possible exceptions of the De Morgan Laws, they are fairly straight-forward to understand. The main diculty you might have with these equivalences is remembering their names. Example2.4.1.Use the logical equivalences above and substitution to establish the equivalence of the statements in Example 2.3.2.Solution.
:(p!q), :(:p_q)Implication Law , ::p^ :qDe Morgan's Law ,p^ :qDouble Negation Law This method is very similar to simplifying an algebraic expression. You are using the basic equivalences in somewhat the same way you use algebraic rules like 2x3x= xor(x+ 1)(x3)x3=x+ 1. Exercise2.4.1.Use the propositional equivalences in the list of important logical equivalences above to prove[(p!q)^ :q]! :pis a tautology. Exercise2.4.2.Use truth tables to verify De Morgan's Laws.2.5. Simplifying Propositions.
2. PROPOSITIONAL EQUIVALENCES 39
Example2.5.1.Use the logical equivalences above to show that:(p_ :(p^q)) is a contradiction.Solution.
:(p_ :(p^q)) , :p^ :(:(p^q))De Morgan's Law , :p^(p^q)Double Negation Law ,(:p^p)^qAssociative Law ,F^qContradiction ,FDomination Law and Commutative Law Example2.5.2.Find a simple form for the negation of the proposition \If the sun is shining, then I am going to the ball game." Solution.This proposition is of the formp!q. As we showed in Example 2.3.2 its negation,:(p!q), is equivalent top^ :q. This is the proposition \The sun is shining, and I am not going to the ball game."Discussion
The main thing we should learn from Examples 2.3.2 and 2.5.2 is that the negation of an implication isnotequivalent to another implication, such as \If the sun is shining, then I am not going to the ball game" or \If the sun is not shining, I am going to the ball game." This may be seen by comparing the corresponding truth tables: pqp! :q:(p!q),(p^ :q):p!qTTFFT TFTTT FTTFT FFTFF If you were to construct truth tables for all of the other possible implications of the formr!s, where each ofrandsis one ofp,:p,q, or:q, you will observe that none of these propositions is equivalent to:(p!q).2. PROPOSITIONAL EQUIVALENCES 40
The rule:(p!q),p^ :qshould be memorized. One way to memorize this equivalence is to keep in mind that the negation ofp!qis the statement that describes the only case in whichp!qis false. Exercise2.5.1.Which of the following are equivalent to:(p!r)! :q? There may be more than one or none. (1):(p!r)_q (2)(p^ :r)_q (3)(:p! :r)_q (4)q!(p!r) (5):q!(:p! :r) (6):q!(:p_r) (7):q! :(p!r) Exercise2.5.2.Which of the following is the negation of the statement \If you go to the beach this weekend, then you should bring your books and study"? (1) If you do not go to the beach this weekend, then you should not bring your books and you should not study. (2) If you do not go to the beach this weekend, then you should not bring your books or you should not study. (3) If you do not go to the beach this weekend, then you should bring your books and study. (4) You will not go to the beach this weekend, and you should not bring your books and you should not study. (5) You will not go to the beach this weekend, and you should not bring your books or you should not study. (6) You will go to the beach this weekend, and you should not bring your books and you should not study. (7) You will go to the beach this weekend, and you should not bring your books or you should not study. Exercise2.5.3.pis the statement \I will prove this by cases",qis the statement \There are more than 500 cases," andris the statement \I can nd another way." State the negation of(:r_ :q)!p. in simple English. Do not use the expression \It is not the case."2.6. Implication.
Definition2.6.1.We say the propositionrimplies the propositionsand write r)sifr!sis a tautology. This is very similar to the ideas previously discussed regarding the,verses$. We user)sto imply that the statementr!sis true, while that statementr!s2. PROPOSITIONAL EQUIVALENCES 41
alone does not imply any particular truth value. The symbol)is often used in proofs as a shorthand for \implies."Exercise2.6.1.Prove(p!q)^ :q) :p.
Exercise2.6.2.Provep^(p!q)! :qis a contingency using a truth table. Exercise2.6.3.Provep!(p_q)is a tautology using a verbal argument. Exercise2.6.4.Prove(p^q)!pis a tautology using the table of propositional equivalences. Exercise2.6.5.Prove[(p!q)^(q!r)])(p!r)using a truth table. Exercise2.6.6.Prove[(p_q)^ :p])qusing a verbal argument. Exercise2.6.7.Prove(p^q)!(p_q)is a tautology using the table of proposi- tional equivalences.2.7. Normal or Canonical Forms.
Definition2.7.1.Every compound proposition in the propositional variablesp, q,r, ..., is uniquely equivalent to a proposition that is formed by taking the disjunction of conjunctions of some combination of the variablesp;q;r;:::or their negations. This is called thedisjunctive normal formof a proposition.Discussion
Thedisjunctive normal formof a compound proposition is a natural and useful choice for representing the proposition from among all equivalent forms, although it may not be the simplest representative. We will nd this concept useful when we arrive at the module on Boolean algebra.2.8. Examples.
Example2.8.1.Construct a proposition in disjunctive normal form that is true precisely when (1)pis true andqis falseSolution.p^ :q
(2)pis true andqis false or whenpis true andqis true.Solution.(p^ :q)_(p^q)
(3) eitherpis true orqis true, andris false Solution.(p_q)^ :r,(p^ :r)_(q^ :r)(Distributive Law) (Notice that the second example could be simplied to justp.)2. PROPOSITIONAL EQUIVALENCES 42
Discussion
The methods by which we arrived at the disjunctive normal form in these examples may seem a littlead hoc. We now demonstrate, through further examples, a sure-re method for its construction.2.9. Constructing Disjunctive Normal Forms.
Example2.9.1.Find the disjunctive normal form for the propositionp!q.Solution.Construct a truth table forp!q:
pqp!qTTT TFF FTT FFT p!qis true when either pis true andqis true, or pis false andqis true, or pis false andqis false.The disjunctive normal form is then
(p^q)_(:p^q)_(:p^ :q)Discussion
This example shows how a truth table can be used in a systematic way to construct the disjunctive normal forms. Here is another example. Example2.9.2.Construct the disjunctive normal form of the proposition (p!q)^ :rSolution.Write out the truth table for(p!q)^ :r:
2. PROPOSITIONAL EQUIVALENCES 43
pqrp!q:r(p!q)^ :rTTTTFFTTFTTT
TFTFFF
FTTTFF
TFFFTF
FTFTTT
FFTTFF
FFFTTT
The disjunctive normal form will be a disjunction of three conjunctions, one for each row in the truth table that gives the truth value T for(p!q)^:r. These rows have been boxed. In each conjunction we will usepif the truth value ofpin that row is T and:pif the truth value ofpis F,qif the truth value ofqin that row is T and:qif the truth value ofqis F, etc. The disjunctive normal form for(p!q)^ :ris then (p^q^ :r)_(:p^q^ :r)_(:p^ :q^ :r); because each of these conjunctions is true only for the combination of truth values of p,q, andrfound in the corresponding row. That is,(p^q^ :r)has truth value T only for the combination of truth values in row 2,(:p^q^:r)has truth value T only for the combination of truth values in row 6, etc. Their disjunction will be true for precisely the three combinations of truth values ofp,q, andrfor which(p!q)^:r is also true. Terminology.The individual conjunctions that make up the disjunctive normal form are calledminterms. In the previous example, the disjunctive normal form for the proposition (p!q)^ :rhas three minterms, (p^q^ :r), (:p^q^ :r), and (:p^ :q^ :r).2.10. Conjunctive Normal Form.Theconjunctive normal formof a propo-
sition is another \canonical form" that may occasionally be useful, but not to the same degree as the disjunctive normal form. As the name should suggests after our discus- sion above, the conjunctive normal form of a proposition is the equivalent form that consists of a \conjunction of disjunctions." It is easily constructed indirectly using disjunctive normal forms by observing that if you negate a disjunctive normal form you get a conjunctive normal form. For example, three applications of De Morgan'sLaws gives
:[(p^ :q)_(:p^ :q)],(:p_q)^(p_q):2. PROPOSITIONAL EQUIVALENCES 44
Thus, if you want to get the conjunctive normal form of a proposition, construct the disjunctive normal form of itsnegationand then negate again and apply De Morgan's Laws. Example2.10.1.Find the conjunctive normal form of the proposition(p^:q)_r.Solution.
(1) Negate::[(p^ :q)_r],(:p_q)^ :r: (2) Find the disjunctive normal form of (:p_q)^ :r: pqr:p:r:p_q(:p_q)^ :rTTTFFTFTTFFTTT
TFTFFFF
FTTTFTF
TFFFTFF
FTFTTTT
FFTTFTF
FFFTTTT
The disjunctive normal form for (:p_q)^ :ris
(p^q^ :r)_(:p^q^ :r)_(:p^ :q^ :r): (3) The conjunctive normal form for (p^:q)_ris then the negation of this last expression, which, by De Morgan's Laws, is (:p_ :q_r)^(p_ :q_r)^(p_q_r):quotesdbs_dbs14.pdfusesText_20[PDF] show that p2 will leave a remainder 1
[PDF] show that the class of context free languages is closed under the regular operations
[PDF] show that the class of turing recognizable languages is closed under star
[PDF] show that the family of context free languages is not closed under difference
[PDF] show that the language l an n is a multiple of three but not a multiple of 5 is regular
[PDF] show that x is a cauchy sequence
[PDF] show that x is a discrete random variable
[PDF] show that x is a markov chain
[PDF] show that x is a random variable
[PDF] show that [0
[PDF] show the mechanism of acid hydrolysis of ester
[PDF] show ? n 2 1 n log np converges if and only if p > 1
[PDF] shredded workout plan pdf
[PDF] shredding diet