Law of syllogism

p → q = “If today is Saturday then library is open”.

q → r = “If the library is open then I must study at the library.

________________________________________________

p → r = “Therefore, if today is Saturday, then I must study at the library”.

The test this argument for validity, consider the truth table:

The rows for which the premises p → q and q → r are true are marked with arrows. Since in each of these cases the conclusion p → r is also true, the argument is valid.

This important argument is known as the law of syllogism. It was one of the contributions to logic by Aristotle (384 – 322 B.C.)

Frequently used rules for making valid arguments.

Ex: Is it a valid argument?

«If I am hungry then I do everything quickly.»

A B

«I do everything slowly». Hence, «I am not hungry».

~B

Our common sense says that the argument is logically sound. The formal notation for the argument is as follows (modus tollense):

A	B	A→ B	~B	~A
F	F	T	T	T
F	T	T	F	T
T	F	F	T	F
T	T	T	F	F

A→ B, ~B

~A

Argument is valid.

Ex: Is the argument valid?

(p → ~q) → (q ˄ ~r), p→~q

q ˄ ~r

Solution: It is valid, since it comes from the argument

p → q, p

q

by replacing p by (p →~q) and q by (q ˄ ~r)

Ex: Is it a valid argument?

If a is 18 then a is divided by 6. (True)

p q

If a is divided by 6 then a is divided by 3. (True)

q r

Therefore «If a is 18 then a is divided by 3».

p r

It is valid because it is a syllogism:

p → q, q→ r

p → r

H/a: Is it a valid argument?

p → q, p→ r

q → r

Prove your answer by a table

H/a: Is it a valid argument?

It is raining or snowing. It is snowing.

Therefore, it is raining.

Prove your answer.

Topic: Boolean algebra

We studied 3 examples of algebras: set algebra, 2-element Boolean algebra and propositional algebra. The properties of these algebras are very similar. It is not by chance. The fact is that these algebras are special cases of a more general type of algebra: Boolean algebra.

Definition: a Boolean algebra is a 6-tuplet:

< B, +, *, ', 0, 1 >,

Where B is a set on which are defined two binary operations: + and *, and a unary operation (complement), denoted '. 0 (zero element) and 1 (unit element) denoted two distinct elements of B.

The following axioms hold for any elements a, b, c є B.

1. Commutative laws:

1.1 a + b = b + a

1.2 a * b = b * a

2. Distributive laws:

2.1 a + (b * c) = (a +b) * (a + c)

2.2 a * (b + c) = (a * b) + (a * c)

3. Identity laws:

3.1 a + 0 = a

3.2 a * 1 = a

4. Complement laws: for any a є B there exists an a' є B, such that:

4.1 a + a' = 1

4.2 a * a' = 0

Precedence: (), ', *, +.

The Duality principle holds for a Boolean algebra. Other laws of the set/propositional/2-element algebras (idempotent, absorption, De Morgan's, etc.) are direct consequences of the axioms 1 - 4.

Theorem 1. (Idempotent law):

(i) a + a = a;

(ii) a * a = a;

Proof:

(i) Statement is true by principle of Duality.

Theorem 2.

(i) a + U = U;

(ii) a * 0 = 0;

Proof

(ii) Statement is true by principle of Duality.

Theorem 3. (Involution law):

(a')' = a;

That is, if (a) a + a' = U, (b) a * a' = 0, (c) a' + a'' = U and (d) a' * a'' = 0, then a=a''.

Proof:

Theorem 4.

(i) U' = 0

(ii) 0' = U

Proof:

(ii) Statement is true by principle of Duality.

Theorem 5. (De Morgan's law):

(i) (a + b)' = a' * b', that is (a + b) * (a' * b') = 0 and

(a + b) * (a' * b') = U

(ii) (a * b)' = a' + b', that is (a * b) * (a' + b') = 0 and

(a + b) * (a' + b') = U

Proof:

(ii) Statement is true by principle of Duality.

Theorem 6.

(i) a + (a * b) = a

(ii) a * (a + b) = a

Proof:

(ii) Statement is true by principle of Duality.

Now

˗ the 2-element Boolean algebra = < {0, 1}, ∧,∨, ‾, 0, 1>

˗ the set algebra is a Boolean algebra = < P(U), ∪, ∩, ‾, ⌀, U>

where P(U) is a power set = set of all subsets of U.

˗ the propositional algebra is a Boolean algebra =

= <{set of all propositions}, ∧,∨, ~, c, t>

where c is any contradictory statement, t is any tautology.

Considering algebras from more and more general points of view, mathematicians introduce more general types of algebras, such as: lattices, groups, semigroups, rings, semirings etc. For example, a Boolean type algebra belongs also to a lattice type (supertype).

H/a: given algebra = <D₇₀, a + b, a * b, a', 1, 70>, where

D₇₀ = {1, 2, 5, 7, 10, 14, 25, 70}, set of divisors of 70;

a + b = l.c.m(a, b) = least common multiple of a and b; a, b ⋲ D₇₀;

a * b = g.c.d(a, b) = greatest common divisor of a and b.

a' = 70/a;

1 is the zero element, 80 is the unit element.

Is it a Boolean algebra? Prove your answer.