2. Propositional Equivalences 2.1. Tautology/Contradiction
Build a truth table to verify that the proposition (p ↔ q)∧(¬p∧q) is a contradiction. 2.2. Logically Equivalent. Definition 2.2.1. Propositions r and s are
Exam 1 Practice Problems
Show that (P ∧ Q) ∨ R is logically equivalent to (P ∨ R) ∧ (Q ∨ R) in two ways. (a) By using a truth table;. (b) By giving an explanation in words. 2
Propositional Logic Discrete Mathematics
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
1. Statements. A (mathematical) statement is a sentence or a
(P ∧ Q) ∧ R P ∧ (Q ∧ R) are logically equivalent. • Law of This is the logical foundation of the 'contrapositive proof'. Page 21. A statement and its ...
Chapter 1 Logic
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
(1) Propositional Logic
) Show that ￢p → (q → r) and q → (p ∨ r) are logically equivalent ? Solution: Page 24. Math 151 Discrete Mathematics ( Propositional Logic ). By
UNIVERSITY OF VICTORIA EXAMINATIONS APRIL 2023 MATH
p) is a tautology. Write a sentence that explains your conclusion. 2. [4] Use known logical equivalences to show that (p _ q) ! r is logically equivalent to. (p
Math 114 Discrete Math
show that (p → q) ∧ (p → r) is logically equivalent to p → (q∧r). Explain in a sentence why your truth table shows that they are logically equivalent. p q.
Intensional Propositional Logic
(q*prs) and (q*s) = (qs*). Several important laws of logic follow at once for example Ladd-Franklin's principle of the antilogism : (pq*r) = (pr*q) = (rq*p).
MATH 300 Problems without solutions
Show that P∧P is logically equivalent to P. Problem 1.3. Are the statement forms (P∧Q)∧R and P∧(Q∧R) logically equivalent? Problem 1.4. Are the
2. Propositional Equivalences 2.1. Tautology/Contradiction
Propositions r and s are logically equivalent if the statement r ? s is a Show that (p ? q) ? (q ? p) is logically equivalent to p ? q. Solution 1.
Math 55: Discrete Mathematics
24 Show that (p ? q) ? (p ? r) and p ? (q ? r) are logically equivalent. By the definition of conditional statements on page 6 using the Com- mutativity
Propositional Logic Discrete Mathematics
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
COM S 330 — Homework 02 — Solutions Type your answers to the
(¬p ? ¬p) ? (q ? r) Associative and Commutative Laws. ? ¬p ? (q ? r). Idempotent law. ? p ? (q ? r). Logical equivalence using conditionals.
(1) Propositional Logic
) Show that ?p ? (q ? r) and q ? (p ? r) are logically equivalent ? Solution: Page 24. Math 151 Discrete Mathematics ( Propositional Logic ). By
Solution Midterm I – Version B
Oct 3 2014 Write the following propositions using p
1 Translating Propositions and English Sentences
Jan 29 2015 Problem 3.1. Prove that (p ? q) ? (p ? r) and p ? (q ? r) are logically equivalent (without using this equivalence from the tables).
SOLUTIONS TO TAKE HOME EXAM 1 MNF130 SPRING 2010
Show that ¬(p ? ¬q) and q ? ¬p are logically equivalent by (c) Prove or disprove that (p ? q) ? r and p ? (q ? r) are equivalent.
Chapter 1 Logic
LOGIC. The conjunction of p and q (read: p and q) is the statement p ? q obtain the truth values of ¬p (¬p ? r)
Section 1.2 selected answers Math 114 Discrete Mathematics
Show that ¬(¬p) and p are logically equivalent. Since (p ? q) ?? ¬p ? ¬q is T in all cases therefore. (p ? q) ? ¬p ... The dual is p ? ¬q ? ¬r.
Math 127: Logic and Proof - CMU
set of notes we have that pqis logically equivalent to (p)q) ^(q)p) Hence we can approach a proof of this type of proposition e ectively as two proofs: prove that p)qis true AND prove that q)pis true Indeed it is common in proofs of biconditional statements to mark the two proofs using
Logical Equivalences - Wichita
Two compound propositions p and q are logically equivalent if p ? q is a tautology ! Notation: p ? q ! De Morgan’s Laws: • ¬ (p ? q) ? ¬ p ? ¬ q • ¬ (p ? q) ? ¬ p ? ¬ q ! How so? Let’s build a truth table!
13 Propositional Equivalences - University of Hawai?i
Constructing New Logical Equivalences We can construct new logical equivalences by applying known logically equivalent statements to show that A B Recall that two propositions p and q are logically equivalent if and only if p $q is a tautology (a k a their truth tables match)
Logic Proofs - Northwestern University
The proposition p ? q read “p if and only if q” is called bicon-ditional It is true precisely when p and q have the same truth value i e they are both true or both false 1 1 4 Logical Equivalence Note that the compound proposi-tions p ? q and ¬p?q have the same truth values: p q ¬p ¬p?q p ? q T T F T T T F F F F F T T
2 Propositional Equivalences 21 Tautology/Contradiction
A second notation often used to mean statements rand sare logically equivalent is r s You can determine whether compound propositions rand sare logically equivalent by building a single truth table for both propositions and checking to see that they have exactly the same truth values
We want to show that P ?¬Q R P ØQ R - University of Oxford
P ?¬Q [P] [R] R ?¬P ¬P ¬R [Q] [¬Q] ¬R ¬R Q ?¬R I need to show Q ? ¬R I hope to getthisbyanapplicationof?Intro So I should try to prove ¬R under theassumptionQ FirstIlookatthe case P Ihopetoget¬R by¬Intro; so I assume R
Are p ? q and p ? (q ? r) logically equivalent?
Solution. 3. Use a truth table to show that ( p ? q) ? ( p ? r) and p ? ( q ? r) are logically equivalent. Solution. 4. Simplify the following statements (so that negation only appears right before variables).
Is P Q true if and P and Q have the same values?
Since p ? q is true if and p and q have the same truth values, in this course we will often build a truth table for the two statements and then remark on whether their columns are the same or different. Example 2.1.3. Prove the following are equivalent using a truth table. We use p ? q ? ¬ p ? q often enough that this has a name.
What is logical equivalence of statement forms P and Q?
The logical equivalence of statement forms P and Q is denoted by writing P Q. Two statements are called logically equivalent if, and only if, they have logically equivalent forms when identical component statement variables are used to replace identical component statements. 2.1 Logical Equivalence and Truth Tables 4 / 9 Logical Equivalence
Are (p?q) ? (p?r) and p? (q?r) logically equivalent?
Show that (p?q) ? (p?r) and p? (q?r) are logically equivalent without using truth tables, but using laws instead. (Hint: s and t are logically equivalent, if s?t is a tautology.
Section 1.2, selected answers
Math 114 Discrete Mathematics
D Joyce, Spring 2018
2.Show that:(:p) andpare logically equivalent.
First, let's see a wordy explanation.
Is:(:p) !pa tautology? Does it come out true no
matter what truth valuephas? There are two cases. In one case,pisT, so:pisF, and:(:p) isT; and since :(:p) andphave the same truth value,:(:p) !pcomes outT. In the other case,pisF, so:pisT, and:(:p) is F; and since:(:p) andpagain have the same truth value, :(:p) !pcomes outTin this case, too. Thus, in both cases,:(:p) !pcomes outT. Thus,:(:p) !pa tautology. Therefore,:(:p) andpare logically equivalent. That was a wordy explanation. You probably gave a much shorter one that's just as good, something like this: Negating interchanges the two truth values, so negating a second time interchanges them back to their original truth values. Since ::phas the same truth value asp, therefore:(:p) !p is a tautology. Another thing you could do is present a truth table like this:p:p::p:(:p) !pTFTT TTFT Then, since the last column only containsTs, it's a tautol- ogy.6.Use a truth table to verify this De Morgan's law:
:(p^q) :p_ :q:pq:(p^q) ! :p_ :qTTF T T F F FTFT F T F T T
FTT F T T T F
FFT F T T T T
Since (p^q) ! :p_ :qisTin all cases, therefore
(p^q) :p_ :q. You could stop one step earlier by noticing that since the columns for:(p^q) and:p_ :qare identical, therefore they're logically equivalent.12.Show that each implication in Exercise 10 is a tautol-
ogy without using truth tables. For these, you can use the logical equivalences given in tables 6, 7, and 8. a)[:p^(p_q)]!q. The following is a list of logically equivalent expressions. Since the last is a tautology, so is therst. Each step uses one of the logical equivalences in oneof the tables to substitute one subexpression for a logically
equivalent subexpression. [:p^(p_q)]!q :[:p^(p_q)]_q (::p_ :(p_q))_q (p_(:p^ :q))_q ((p_ :p)^(p_ :q))_q (T^(p_ :q))_q (p_ :q)_q p_(:q_q) p_T T There are many other routes you could take to reduce the original expression toT. This was just one of them. The other parts of 10 are similar. Here's how 10c might be proved. p^(p!q)!q p^(:p_q)!q (p^ :p)_(p^q)!qF_(p^q)!q
p^q!q :(p^q)_q (:p_ :q)_q :p_(:q_q) :p_T T14.Determine whether (:p^(p!q))! :qis a tautology.
The easiest way is simply to use a truth table.pq(:p^(p!q))! :qTTF F T T FTFF F F T T
FTT T T F F
FFT T T T T
You'll note that the third row does not have aTin the! column, so it's not a tautology. Instead of using a truth table, you could consider the sin- gle case whenpisFandqisT, and show that (:p^(p! q))! :qcomes outF.20.Show that:(pq) andp !qare logically equiva-
lent. This is an important logical equivalence and well worth memorizing. The proof is easy by a truth table and is omit- ted here. 135.Find the dual of each of the following propsitions.
a)p^:q^:r. The dual isp_:q_:r. Just turn all the ^'s into_'s. b)(p^q^r)_s. The dual is (p_q_r)^s. Just interchange ^'s and_'s. c)(p_F)^(q_T). The dual is (p^T)_(q^F). Besides interchanging^'s and_'s, be sure to interchangeT's andF's, too.
46 and 48.Construct truth tables for NAND and NOR.pqpNANDqpNORqTTFF
TFTF FTTF FFTT50.Show that NOR, denoted#, is functionally complete.
As described above problem 43, a collection of logical op- erators is calledfunctionally completeif every compound propsition is logically equivalent to a compound proposition involving only logical operators in the collection. In prob- lem 43, the three logical operators^;_, and:were shown to be functionally complete. All we have to do is show that these three operators can each be described in terms of#. Indeed, by problem 43, we only have to consider two of these operators. a)Show thatp#pis logically equivalent to:p. Just use a truth table. b)Show that (p#q)#(p#q) is logically equivalent to p^q. Again, a truth table is the simplest way. c)Since problem 44 shows that:and^form a func- tionally complete collection of logical operators, and each of these can be written in terms of#, therefore#by itself is a functionally complete collection of logical operators. One implication of this result is that all the logical ciruitry of a computer can be constructed from only one kind of logical gate, a nor-gate.Math 114 Home Page athttp://math.clarku.edu/
djoyce/ma114/ 2quotesdbs_dbs17.pdfusesText_23[PDF] show that 2^p 1(2p 1) is a perfect number
[PDF] show that 4p^2 20p+9 0
[PDF] show that a sequence xn of real numbers has no convergent subsequence if and only if xn ? ? asn ? ?
[PDF] show that etm turing reduces to atm.
[PDF] show that every infinite turing recognizable language has an infinite decidable subset.
[PDF] show that every tree with exactly two vertices of degree one is a path
[PDF] show that f is continuous on (?? ?)
[PDF] show that for each n 1 the language bn is regular
[PDF] show that if a and b are integers with a ? b mod n then f(a ? f(b mod n))
[PDF] show that if an and bn are convergent series of nonnegative numbers then ? anbn converges
[PDF] show that if f is integrable on [a
[PDF] show that if lim sn
[PDF] show that p ? q and p ? q are logically equivalent slader
[PDF] show that p ? q and p ? q ? p ? q are logically equivalent
