CH 3 Propositional Logic Flashcards
Define a proposition.
Define the 5 connectives we will use.
How many rows are in a truth table with n variables?
Define a valuation.
Define a tautology.
Define a contradiction.
A valuation is an assignment of truth values T and F to the variables. So, with n variables, there are 2n valuations. A tautology is a formula which is given the value T by every valuation, and a contradiction is one which is given the value F by every valuation.
When is a formula in disjunctive normal form, DNF?
State and prove a result on when a function can be represented by a formula in DNF.
When is a formula in conjunctive normal form, CNF?
State and prove a similar result for CNF.
Define a deduction system.
Define a proof.
Define a theorem.
Modus Ponens
Give a deduction system for propositional logic.
Define a hypothesis.
State the Deduction Theorem.
State and prove the Proof by Contradiction theorem.
Define logically valid.
When is a deduction system sound, and when is it complete?
How do we prove a deduction system is sound?
State a theorem on the deduction system for propositional logic, on having a countable set of variables.
Define a formula A being a ‘logical consequence’ of a set of formulae, and state a more general theorem than above.
Restate the above theorem in terms of a set of ‘consistent’ formulae.
… Finish Soundness and Competeness proof/section - more revision required.
State Theorem 3.10 on when there exists a valuation such that v(A) = T.
State and prove the Compactness Theorem.
Prove: if every finite subgraph of a graph can be coloured, then the entire graph can be coloured—a result that follows from the Compactness Theorem.
