Let us denote the true constant by 1 and the false constant by 0. We write v( α) = 1, if the  proposition α is true and we write v( α) = 0, if it is a false proposition. Now we may treat v as a function which assigns every proposition to its logical value. For example:

The final value of the complex proposition depends on the values of its subformulas according to the following equalities:

In this manner

are false propositions, while

are true propositions.

the above-mentioned equalities define over the set of logical values {0,1} four two-argument operations ∧ , ∨ , → , ↔ and one one-argument operation ¬ .

The Boolean algebra enables us to interpret an arbitrary formula defined in the propositional calculus. For this aim we need to interpret all propositional variables occuring in the formula and then apply the operations of the two-element Boolean algebra.

The logical constants true and false are interpreted respectively as 1, 0 in the two-element Boolean algebra.

If we are given a valuation of propositional variables, we can determine the logical value of any arbitrary formula according to the following recursive definitions:

• The negation  ¬ α is true at the valuation v, if  α is false at the same valuation and otherwise false.
• The conjunction (α ∧ β) is true at the valuation v, if  α and  β are both true at the valuation v, and otherwise false.
• The alternative (disjunction) (α ∨ β) is true at the valuation v, if at least one  α  or β is true at the valuation v, and otherwise false.
• The implication (α → β) is true at the valuation v, if α is false or β is true at the valuation v, and otherwise false.
• The equivalence (α ↔ β)  is true at the valuation v, if  the value of both formulas α and β are equal, and otherwise false.

If v is a valuation and α is a formula, then by α(v) we denote the value of the formula αat the valuation v. In particular, when  α is a propositional variable, e.g. p, then  α(v) = v(p). Below-introduced tables are sometimes named logical matrices (or logical tables - see Fig. 6.2.1). They define the semantics of the propositional formulas  at the given logical values of its variables. 

Fig. 6.2.1 The semantics of formulas of propositional calculus.

Example 6.2.1
Let be given a valuation v such that  v(p)=1, v(q)=1 and v(r)=0. Now, consider the formula α

In order to calculate the value of the formula at the valuation v we will determine succesively the values of its subformulas :

(p → q)(v) = 1,
(r → q)(v) = 1,
((p → q) ∧(r → q))(v) = 1,
(p ∨ q)(v) = 1,
((p ∨ q) → r)(v) = 0

Finally, because the value of the predecessor is 1 and the value of the successor is 0, then α(v) = 0.

Let us notice that the semantics of the implication is not completly intuitive. The implication p → q take the value true providing that the predecessor p is a false proposition regardless of the successors' value. Therefore, the proposition "2+2=5 → (every natural number is even)" is true because both of its clauses are false as well as "2+2=5 → 2+2=4" is also a true proposition because the implication's predecessor is a false proposition.

Question 6.2.1: Find the value of the following expressions in the two-element Boolean algebra:

1. (((1 ∧ 1 ) ∧ 0) → 1)
2. ((0 ↔ 1) → (( ¬ 0 ∧ 0) → 0))
3. ((((1 ∨ 1) ∨ 0 ) → ¬ (0 ↔ 1)) ↔ 0 ).

The formula presented in the example 6.2.1 is satisfiable because there are values of p, q, r for which the formula is satisfied. In fact, if we assume v(r)=1 thus, according to the definition of the implication, we obtain

The logical functors ¬ , ∧ , ∨ , → have a common property called extensionality. Namely, the logical value of the propositions constructedby means of  them depends only on the logical value of their arguments and not on the sense of the propositions used.  

Example 6.2.2
(a) The  value of the proposition: "Everybody sitting in this lecture hall is interested in logic or propositional calculus is the basis of logic" depends only on the value of clauses "Everybody sitting inthis lecture hall is interested in logic" and "propositional calculus is the basis of logic". Furthermore this proposition is true providing that at least one of the  above-mentioned clauses is true.
(b) The logical value of the sentence "I think, that everybody sitting in this lecture hall is interested in logic or the propositional calculus is the basis of logic" does not depend on clauses value but on that what I think. Although the expression "I think, that" can be recognized as a new sentences creating operator, it does not have the extensionality property. This type of functors do not belong to the subject of the propositional calculus research.

Question 6.2.2: Let's assume that Peter is the best student. What is the value of the sentence "It seems that Peter is the best student"?

Answer: The answer is unknown. Our feelings could be in confict with the  facts. "It seems" is a kind of a propositional connective but it has no  extensionality property.

Now we may rise a question: how many different extensional functors can be constructed?

Let us think firstly about one-argument functors. In other words, we try to find a number of all one-argument functions f such that f : {0,1} → {0,1}. Because there are exactly 2² different logical matrices (see Fig. 6.2.2(a)), the answer is 4.

Fig. 6.2.2(a) The table of all one-argument propositional functors.

Similarly, we may consider a case of two-argument propositional functors, i.e. we want to estimate a number of all different two-argument functions f such that f:{0,1} × {0,1} → {0,1}). Because there are exactly four different argument's arrangements, the number of two-argument propositional functors is equal to the number of possible four-element sequences. Or there are 2⁴=16 different two-argument functors (see Fig. 6.2.2(b)).

Fig. 6.2.2b The table of all two-argument propositional functors.

Notice that  f₅ and  f₁₅ corresponds exactly to the conjunction and the alternative, respectively. Even though, there are 16 different functors, we mainly use only conjunction ∧ , alternative ∨ and implication → . Why? Well, these functions are closest to the natural language logical conjunctions and, by using only one of them and the negation,  we may construct any other two-argument functor. It is worth to study more precisely the functor marked at the Fig. 6.2.2(b) with number 12. We name it Sheffer's functor and denote with the symbol |. Sheffer's functor itself allows to construct any other one- and two-argument propositional functors. The Reader is asked to check by himself that the following equalities  define  negation, alternative and conjunction:

¬ p = p|p,

p ∨ q = (p|p)|(q|q),

p ∧ q = (p|q)|(p|q).

Question 6.2.3 Define using negation and alternative the following functors: f₅, f₈, f₁₃ and f₁₆.

« previous section

next section »