Logical equivalences and De Morgan's laws
The usual equivalences of propositional calculus, De Morgan's laws, negating a formula and rewriting a program condition without negation.
- 23 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
A few cards from the deck
Logical equivalence: what is it?
Show the answer
A relation between two formulas that have the same value for all values of their variables, hence the same truth table.
It is written ≡. Two equivalent formulas are interchangeable: one can replace the other in any formula or program condition.
Which formula is equivalent to ¬(p ∧ ¬q)?
- ¬p ∨ q
- ¬p ∧ q
- ¬p ∨ ¬q
- p ∨ q
Show the answer
¬p ∨ q
De Morgan: ¬(p ∧ ¬q) ≡ ¬p ∨ ¬¬q, and ¬¬q ≡ q. Two mistakes are common: keeping the ∧, or forgetting to simplify the double negation.
By De Morgan, ¬(x > 0 ∧ y > 0) is equivalent to x … 0 … y ≤ 0.
Show the answer
By De Morgan, ¬(x > 0 ∧ y > 0) is equivalent to x ≤ 0 ∨ y ≤ 0.
The ∧ becomes ∨ and each comparison is negated: the opposite of x > 0 is x ≤ 0, not x < 0, since the case x = 0 must stay.
De Morgan's law for ∧: what is it?
Show the answer
¬(p ∧ q) ≡ ¬p ∨ ¬q: the negation of an "and" is the "or" of the negations.
For "p and q" to be false, it is enough that one of them is. Negation therefore distributes while switching the connective.
A site shows "access denied" when
not (age >= 18 and verified). In which cases does it deny access?- If the age is under 18, or the account is not verified, or both
- Only if the age is under 18 and the account is not verified
- Only if the age is under 18
- Only if the account is not verified
Show the answer
If the age is under 18, or the account is not verified, or both
not (A and B)is(not A) or (not B): one missing condition is enough to deny. Writing anandin place of theorwould let in a minor whose account is verified.