Definitions
What is a proposition?
A proposition is a “declarative sentence that is either true or false”. For example - questions and commands are not propositions
A proposition might also be called a statement
Atomic Propositions
A statement/proposition is called atomic, if it has no connectives or quantifiers. It is called compound otherwise.
Syntax
infinite set of atomic propositions Two logical connectives ¬ (not) and (or) Set of formulas of propositional logic is the smallest set satisfying the following conditions:
- Every atomic prop is a member of
- If is a member of , so is ¬
- If and are members of , so is
Derived Connectives
: : :
Exercise
According to the Pigeonhole Principle, if we try to place n+1 pigeons in n pigeonholes, then at least one pigeonhole must have two or more pigeons. For and , let the atomic proposition denote that the pigeon is placed in the the pigeonhole. Write down a formula expressing the Pigeonhole Principle. What is the length of your formula as a function of n?
SOLUTION
Suppose we also had a connective Then using that, the formula becomes
Now we can derive the logical connective Let Let Then the original formula becomes
Length of the formula :
Shorter solution? I do not have it right now.
Satisfiability and Validity
A formula is said to be satisfiable if there is a valuation v such that . We write to indicate that . The formula α is said to be valid if for every valuation v. We write to indicate that α is valid. We also refer to valid formulas of propositional logic as tautologies
Proposition
Let α be a formula. α is valid iff ¬α is not satisfiable.
Vocabulary
Since testing the validity of a formula involves checking the truth value across an uncountable number of valuations, we have a way to decrease this. We check the effect of a valuations on the atomic prop mentioned in
We inductively define
I mean still we will have to look at uncountable number of valuations right? This is still not decreasing the number of valuations that we need to check? So why do we have this?
Axiomatisation
I will use instead of . (It is just easier to read) a good resource : https://krchowdhary.com/axiomatic.pdf
Axiom Schemes:
MP :
The first three axioms are tautologies
Compactness and Strong Completeness
Logical Consequence
Let X be a set of formulas and v be a valuation. We write to denote for every formula . A formula α is a logical consequence of X , written , if for every valuation v such that it is also the case that
Derivability
Let X be a set of formulas and v be a valuation. We say that a formula α is derivable from X, written if there exists a sequence of formulas such that and for , is either a member of X , or an instance of one of the axioms of AX, or is derived from , using the inference rule MP.
Motivation for and Logical Consequence
It is possible that sometimes are not concerned if a given logical formula is always true, rather we might be interested that if under some circumstances, is true. In this situation, we can represent these “circumstances” or “constraints” using a set of formulas . And now we can ask under and a valuation , can be true?
: is a logical consequence of X : is derivable from X
Theorem: Strong Completeness
Let and , Then iff
Good Resources to check this?
- Logic in Action : Need to test this