| « previous section | next section » |
The subjects of propositional calculus' research are "propositions", i.e. a natural language sentences which can be evaluated with two disjoint values: true and false. We do some operations over propositions which lead to more complicated propositions. In this way we create the calculus the idea of which is similar to numbers calculi and gives us patterns for our reasoning and proofs.
Of course, there are natural language sentences which are not propositions in the sense of propositional calculus. If we consider the question: "What's the weather like?", we can not ascribe any value to it (true or false). However, the sentence "It is raining." gives the possibility to evaluate its value as true or false. Below there are some examples of this type (i.e. other propositions):
"Warsaw is the capital of Poland."
"Wistula is the name of the river in Poland."
" Alps are the the highest mountains in the world."
"3+2 = 5."
"For every real number x, x * x > 0."
In a natural language, complex sentences are constructed from
simple ones by means of conjunctions. The same applies to
propositional
logic: we will construct propositions by means of the logical
connectives
(or
propositional connectives): not, and, or, implies, if and only if.
Instead of the words we will use symbols: ¬
for negation,
∧
for conjunction,
∨
for alterative,
→ for implication, ↔
for equivalence.
Let us denote by p the proposition "x is an even number", by q the proposition "x is an odd number" and by r the proposition "x is a natural number". Then, the proposition "If the number x is natural, then it is either even or odd" can by written down in the form of the below-mentioned formula:
Notice, that the same formula suits other propositions (e.g. the proposition "If x>y then x>0 or y>0" where r means "x>y", p means "x>0" and q means "y>0"). Therefore, we can treat this formula as a function related to variables p, q, r, the value of which are true or false propositions. The whole formula's validity is strongly determined by the type of propositions which are ascribed to the variables of the formula.
Variables the value of which are propositions are called propositional variables. Using propositional variables, the logical constants true and false, and the propositional connectives we will construct the set of all well-formed expressions, i.e. formulas (or schemes of formulas) of the propositional calculus.
Definition 6.1.1
Let V be
a set of propositional variables. The set of formulas of the
propositional calculus is the least set (in the sense of
inclusion) of
expressions which include the set V, the truth symbols true and
false, and such that when α
and β
are
formulas, then ¬ α, (α
∧ β), (α
∨
β), (α
→
β), (α
↔
β) are
also formulas.
Every formula we use in building up a formula α, including α itself, is called a subformula of α.
Example 6.1.1
Let p, q, r be propositional variables. Then the following expressions are examples of formulas of propositional calculus:
(( ¬
p → q) →
(p ∧ q)), ((p ∧
q) → ¬
( p ∨ q)), ((p →
q) → q), ( ¬
(p ∧ q) ∨
¬ (p ∧
q)).
Question 6.1.1 Using formulas of propositional calculus write down:
(1) "Grass snake is big but harmless" assuming that p= "Grass snake is big", q = "Grass snake is harmless".
(2) "When a crocodile spots its victim, then it carefully swims to it and suddenly attacks when it is close enough" assuming that p = "Crocodile spots victim", q = "(crocodile) swims to it", r = "swims carefully", s = "suddenly attacks", t = "is close enough".
Example 6.1.2
In mathematics we often use the expression: "p is the necessary and sufficient condition for q". This sentence can be transformed onto two propositions of the propositional calculus:
( ¬ p → ¬ q) (p is necessary condition)
(p → q) (p is sufficient condition)
p is the necessary condition for q because, if p does not hold, then q does not hold too. p is the sufficient condition for q because, if only p holds, then q holds too. Let's consider for example the sentence: "The necessary and sufficient condition for a number to be 3-divisible is that the sum of all its digits is divisible by 3". We may split this proposition into the following two conditions:
if the sum of a number's digits is not divisible by 3, then this number is not be divisible by 3 (necessary condition for number 3-divisiblity is that the sum of all its digits is divisible by 3),
if the sum of a number's digits is 3-divisible, then this number is divisible by 3 (sufficient condition for number 3-divisibility is that the sum of all its digits is divisible by 3).
Remark. In the next sections of this lecture we sometimes do not write down all formally-needed brackets. Similarly to arithmetics we assume the following priority of logical operations: ¬ , ∧ , ∨. According to this ¬ p ∧ q ∨ r ∧ p means ((( ¬ p) ∧ q) ∨ ( r ∧ p)).
Question 6.1.2 For each of the sentences presented below find out if they are propositions in the sense of propositional calculus:
| « previous section | next section » |