propositional equivalences Flashcards
A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a
tautology
A compound proposition that is always
false is called a
contradiction
A compound proposition that is neither a tautology nor a
contradiction is called a
contingency
Compound propositions that have the same truth values in all possible cases are called
logically equivalent.
The compound propositions p and q are called
logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
De Morgan laws
TABLE 2 De
Morgan’s Laws.
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
De Morgan’s laws tell us
how to negate conjunctions and how to negate disjunctions
When using De Morgan’s
laws, remember to change
the logical connective
after you negate.
A compound proposition issatisable if there is
an assignment of truth values to its variables that
makes it true
When no such assignments exists, that is, when the compound proposition is false
for all assignments of truth values to its variables, the compound proposition is
unsatisfiable
When we find a particular assignment of truth values that makes a compound proposition
true, we have shown that it is satisable; such an assignment is called a
solution of this particular satisfiability problem
is represented by a 9 × 9 grid made up of nine 3 × 3 subgrids
A Sudoku puzzle
9 × 9 grid made up of nine 3 × 3 subgrids is know as
blocks
