A Proposition is a declarative sentence, which may be shown to be either true, or false, whether the statement is true or false is not – however – relevant. Both “1+2-=3” and “1+2=4” are example of propositions. Predicate logic allows us to explore the truthfulness of a statement, it has an expressive power which propositional logic does not.
Propositional Operators
Operators can act on the values of propositions, altering them accordingly:
Negation
The negation operator inverts the proposition, for example if we have a proposition $$ P=\mbox{ Today is Tuesday} $$, then the negation of this proposition, $$\neg P = \bar P = \mbox{ It is not the case that today is Tuesday}$$.
Conjunction
The conjunction operator is the same as ‘AND’ in binary algebra, so if we have two propositions, such that $$P=\mbox{ Today is Tuesday} $$ and $$ Q=\mbox{ It is Sunny Today} $$ then the conjunction is $$ P \wedge Q =\mbox{ Today is Tuesday and Today is Sunny}$$
Disjunction (Inclusive)
The disjunction operator (or more specifically the inclusive disjunction operator) is the same as ‘OR’ in binary algebra, so the disjunction of two propositional variables will be true if either of the two propositions are true, or if both are true, so if we have two propositions, such that $$P=\mbox{ Today is Tuesday} $$ and $$ Q=\mbox{ It is Sunny Today} $$ then the disjunction is $$ P \vee Q =\mbox{ Today is Tuesday, or it is Sunny Today}$$
Disjunction (Exclusive)
This exclusive disjunction operator is the same as XOR in binary algebra, and is based on the premise that only if one or other (not both) of the propositions is true, will the exclusive disjunction be true. Using our example of $$P$$ and $$Q$$, we can say that $$P \oplus Q =\mbox{ Either today is Tuesday or it is Sunny Today}$$
Conditional Statement
The conditional statement is also known as implication, if one proposition is true, then it implies than a further proposition must be true. Again using our running example, we would say that $$\mbox{If } P \mbox{ then } Q $$, which would be written as $$ P \to Q = \mbox{ If today is Tuesday then it is Sunny}$$
Bi-Conditional Statement
The bi-conditional statement is an extension of the conditional statement, two propositions are bi-conditional if they are always true when the other is true and never else. With our example, $$ P \leftrightarrow Q = \mbox{ If today is Tuesday, then it is Sunny. If it is Sunny Today it must be Tuesday}$$ . This is a marked difference from the conditional statement, the bi-conditional statement can also be expressed as $$P \leftrightarrow Q = \left(P \to Q \right) \wedge \left(Q \to P \right) $$
Predicate Logic
Predicate logic is more concerned with whether a proposition is true or not, so for example if we have a proposition $$P \left( x \right) = x>3$$ then P(4) will be true, P(1) will be false, etc. We can use this methodology in lots of applications, for example to verify the output of an algorithm we can define input and output conditions in terms of predicate logic, and then verify the output matches our expectation to prove the validity of the algorithm.
We can use quantifiers to limit – or qualify – the range of acceptable values in a predicate function. There are two main quantifiers we are interested in here:
Universal Quantifier
The universal quantifier means that the proposition should only be considered for all values of the given variable, for example $$ \forall _x P\left( x \right) = x + 1 > x $$ shows that for all real values of $$ x $$, the $$P\left( x \right) holds true$$
Existential Quantifier
The existential quantifier means that the proposition will only hold true for one or more values of the given variable (or, there exists a value for which the proposition holds true), so for example $$ \exists _x P\left( x \right) = x^2 > 10 $$ will only hold true for positive, integer values of $$ x $$ less than 4.
References:
- Nick Holliman – Formal Aspects Set Theory – Lecture 1
- Nick Holliman – Formal Aspects Set Theory – Lecture 2
