propositional logic
(2.8 hours to learn)
Summary
Propositional logic is a logical formalism where the variables correspond to atomic sentences which are either true or false. Formulas are constructed using the connectives AND, OR, NOT, and IMPLIES. The semantics can be defined in terms of "truth tables," or equivalently boolean functions.
Context
-this concept has no prerequisites-
Goals
- understand the meanings of the propositional connectives AND, OR, NOT, and IMPLIES
- be able to evaluate the truth value of a propositional formula given the truth values of the variables
- be aware of ways in which IMPLIES does not correspond to our intuitive notions of implication
- be able to manipulate propositional formulas (e.g. with distributive laws, de Morgan’s laws)
- be able to define mathematically: a truth assignment, whether a formula is satisfied
- define what it means for one set of formulas to tautologically imply another
Core resources (read/watch one of the following)
-Free-
→ Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Location:
Lecture sequence "Propositional logic"
Other notes:
- Click on "Preview" to see the videos.
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
→ Coursera: Logic: Language and Information (2014)
An introductory logic course geared towards philosophers.
-Paid-
→ Artificial Intelligence: a Modern Approach
A textbook giving a broad overview of all of AI.
Location:
Section 7.4, "Propositional logic: a very simple logic," pages 204-211
Other notes:
- See Section 7.2 for a description of the Wumpus World.
→ The Language of First-Order Logic
An undergraduate logic textbook aimed at philosophers, with an educational software package.
- Chapter 3, "Conjunctions, disjunctions, and negations," up through Section 3.7, "Satisfiability and logical truth," pages 35-58
- Chapter 4, "Conditionals and biconditionals," up through Section 4.2, "Biconditional symbol," pages 91-97
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
- Section 1.1, "The language of sentential logic," pages 13-19
- Section 1.2, "Truth assignments," pages 20-27
See also
-No Additional Notes-