A proposition is a statement that can be true or false. Propositional logic uses true statements to form or prove other true statements.
There are two parts to propositional logic:
The order of operations is !, *, +, =>, <=>
This definition can be decribed by the following unambiguous BNF grammar:
The value of a proposition can be found by making a truth table from its components.
Example: (p*q)+r
p q r p*q (p*q)+r 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1
+ and * are communitive: p+q <==> p+p p*q <==> q*p + and * are associative: (p+q)+r <==> p+(q+r) (p*q)*r <==> p*(q*r) + is distributable over *: p+(q*r) <==> (p+q)*(p+r) * is distributable over +: p*(q+r) <==> (p*q)+(p*r) DeMorgan's Theorem: !(p+q) <==> !p * !q !(p*q) <==> !p + !q Complementation: !(!p) <==> p
G:P => {T,F} Interpretation G takes a set of propositions P and returns an element T or F. G |= P P is true for interpretation G. '|=' is a single symbol known as a double turnstyle. G != P P is not true for interpretation G.
This theorem is the basis of reasoning in propositional logic.
Modus Ponens
If p=>q is true and p is true, then q must be true. p=>q !p+q p p --- --- q q If a drunk person swerves while driving and the person is drunk, then the car is swerving.Modus Tolens
If p=>q is true and q is false, then p must be false. p=>q !p+q !q !q --- --- !p !p If a drunk person swerves while driving and the car is not swerving, then the person is not drunk.And-Elimination
If p*q is true, the p is true and q is true p*q --- pOr-Introduction
If p is true, then p+q is true. p --- p+qDouble-Negation Elimination
The negative of a negative is a positive. !!p --- pResolution
Because b and !b cannot both be true, one of the other literals in a disjunction must be true. a+b * !b+c !a=>b * b=>c ---------- ------------- a+c a=>c Resolution is the most powerful of the rules of inference since it allows us to create new clauses from what we know.
This is all we have to reason. Other forms are considered bad logic:
If a drunk person swerves while driving and the car is swerving, then the person may or may not be drunk.
Any two clauses in a valid CNF with one set of complementing literals can be disjoined together to create a new clause.
Within the new clause duplicate literals can combined to simplify it.
Example: C1*C2 <==> T
C1: !a+b+c+d C2: a+b+c+e -------------------- C3: b+b+c+c+d+e (by resolution) C3: b+c+d+e Thus C1*C2*C3 <==> TNote that resolving two clauses with more than one set of complementing literels is not useful.
Example: C1*C2 <==> T,
C1: a+b C2: !a+!b ------------------- C3: a+!a C4: b+!bSince (a+!a) is T regardless of the state of a, the CNF becomes C1*C2*T*T. Conjunction of T with a true statement does not add anything to the statement.
If the clauses in a CNF can be resolved to an empty set {}, then the CNF is unsatisfiable.
Example: K:C1*C2
C1: b C2: !b ---------------- C3: {}
An empty set is implicitly defined as false. Any statement P, made up of the disjunctions p1+p2+...+pn, can also be represented as P+F. The disjunction of F does not change the truth of P. If we resolve P+F and !P+F, we get F. Conjuncting F with the original statement C1*C2*F, shows that the statement is always false. This means that the negation of that statement is always true.
If a clause (C) is conjoined with a valid CNF (K) and the resulting CNF (K*C) is unsatisfiable, then C must be unsatisfiable and thus its inverse (!C) must be valid.
Proof: Given that K*!C is unsatisfiable.
!(K*!C) valid by definition !K+!!C by DeMorgan !K+C by double negation K=>C If K is true then C is true.
Given any rule base K, and a negated conclusion !C we can prove that K implies C if and only if K and !C implies an empty statement {}. R=>C iff R*!C=>{}
Example: K:C1*C2*C3 C:r
C1: p C2: p=>q C3: q=>r C4: !r ---------------- C5: !p+q (C2) C6: !q+r (C3) C7: !p+r (C5,C6) C8: r (C1,C7) C9: F,{} (C4,C8)Since !C results in a contradiction, C must always be true. Back