The document discusses concepts in discrete mathematics, focusing on propositional logic, including tautologies, contradictions, and logical equivalences. It explains the principles of propositional satisfiability using examples such as Sudoku puzzles and provides proofs for logical equivalences. The document also poses mathematical queries related to infinite series and logical assertions.
The document discusses concepts in discrete mathematics, focusing on propositional logic, including tautologies, contradictions, and logical equivalences. It explains the principles of propositional satisfiability using examples such as Sudoku puzzles and provides proofs for logical equivalences. The document also poses mathematical queries related to infinite series and logical assertions.
The document discusses concepts in discrete mathematics, focusing on propositional logic, including tautologies, contradictions, and logical equivalences. It explains the principles of propositional satisfiability using examples such as Sudoku puzzles and provides proofs for logical equivalences. The document also poses mathematical queries related to infinite series and logical assertions.
The document discusses concepts in discrete mathematics, focusing on propositional logic, including tautologies, contradictions, and logical equivalences. It explains the principles of propositional satisfiability using examples such as Sudoku puzzles and provides proofs for logical equivalences. The document also poses mathematical queries related to infinite series and logical assertions.
The Foundations: x y ( x y ) Logic and x( | x )
1 Proofs x 1 ? x x 1 x ?
RIZOAN TOUFIQ ASSISTANT PROFESSOR DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING RAJSHAHI UNIVERSITY OF ENGINEERING & TECHNOLOGY Propositional Equivalences
Section 1.3 Section Summary
Tautologies, Contradictions, and Contingencies.
Logical Equivalence – Important Logical Equivalences – Showing Logical Equivalence Propositional Satisfiability – Sudoku Example Tautologies, Contradictions, and Contingencies A tautology is a proposition which is always true. – Example: p ∨¬p A contradiction is a proposition which is always false. – Example: p ∧¬p A contingency is a proposition which is neither a tautology nor a contradiction, such as p
p ¬p p ∨¬p p ∧¬p T F T F F T T F Logically Equivalent
Two compound propositions p and q are logically equivalent if
p↔q is a tautology. We write this as p⇔q or as p≡q where p and q are compound propositions. This truth table shows that ¬a ∨ b is equivalent to a → b. – p: ¬a ∨ b – q: a → b
a b ¬a ¬a ∨ b a→ b p ↔q T T F T T T T F F F F T F T T T T T F F T T T T De Morgan’s Laws Augustus De Morgan 1806-1871
This truth table shows that De Morgan’s Second Law holds.
p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Key Logical Equivalences Key Logical Equivalences (cont) More Logical Equivalences Equivalence Proofs
Example: Show that ⌐(p∨(⌐p ∧q)) is logically equivalent
to ⌐p∧⌐q Solution: Equivalence Proofs
Example: Show that (p∧q)⟶(p∨q) is a tautology.
Solution: Propositional Satisfiability
A compound proposition is satisfiable if there is an
assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable. A compound proposition is unsatisfiable if and only if its negation is a tautology. Questions on Propositional Satisfiability Example: Determine the satisfiability of the following compound propositions:
Solution: Satisfiable. Assign T to p, q, and r.
Solution: Satisfiable. Assign T to p and F to q. Solution: Not satisfiable. Check each possible assignment of truth values to the propositional variables and none will make the proposition true. Notation
Needed for the next example.
Sudoku
A Sudoku puzzle is represented by a 99 grid made up
of nine 33 subgrids, known as blocks. Some of the 81 cells of the puzzle are assigned one of the numbers 1,2, …, 9. The puzzle is solved by assigning numbers to each blank cell so that every row, column and block contains each of the nine possible numbers. Example Encoding as a Satisfiability Problem Let p(i,j,n) denote the proposition that is true when the number n is in the cell in the ith row and the jth column. There are 99 9 = 729 such propositions. In the sample puzzle p(5,1,6) is true, but p(5,j,6) is false for j = 2,3,…9 Encoding (cont)
For each cell with a given value, assert p(i,j,n), when the cell in row i and column j has the given value. Assert that every row contains every number.
Full Logical Foundations of Computer Science International Symposium LFCS 2018 Deerfield Beach FL USA January 8 11 2018 Proceedings 1st Edition Sergei Artemov PDF All Chapters
Full Logical Foundations of Computer Science International Symposium LFCS 2018 Deerfield Beach FL USA January 8 11 2018 Proceedings 1st Edition Sergei Artemov PDF All Chapters
