Logic Expression

Free Software for Developers

Negation

Theoretical basic

TERMS AND DEFINITIONS OF THE MATHEMATICAL LOGIC

Some terms of mathematical logic is used in mathematic.

Definition 1. proposition is every meaningfull predicament for which following two principles are valid:

1. Principle of exclusion of third. Every proposition has at least one of the properties of truthness or falseness, i.e. there is no proposition that can be niether true nor false.

2. Principle of contradiction. Every proposition has at most one of the properties of truthness or falseness, i.e. there is no proposition that can be both truth and false.

According to this definition, every proposition has only one value of truthness: it can be either truth or false.

Definition 2. In mathematic, truth proposition is called theorem.

Truth proposition has value '1' (True), false proposition has value '0' (False).

Operations are defined over elements '1' and '0'. Basic operations are: negation ('#'), conjunction ('*'), disjunction ('+'), exclusive disjunction ('!+'), implication ('=>') and equivalency ('<=>').

NEGATION '#'

Negation of proposition p is written #p. proposition #p is true if and only if the proposition p is false. proposition #p is false if and only if proposition p is true. '#' is unary operator.

Truth table for negation looks like this:

P  #p

0   1

1   0

CONJUNCTION '*'

If p and q are two propositions, proposition 'p and q' is called conjunction (or product) of propositions p and q. It is written p*q.

Conjunction of two propositions p and q is true only when both p and q are true. This is shown in the following table:

p  q  p*q

0  0   0

0  1   0

1  0   0

1  1   1

DISJUNCTION '+'

If p and q are two propositions, than proposition 'p or q' implies that either q is valid or q is valid or both p and q are valid propositions.

This complex proposition is called disjunction (or summation) of propositions. and is denoted as p+q.

Disjunction p+q is true if at least one of p and q is true. In this case, truth table is defined as:

p  q  p+q

0  0   0

0  1   1

1  0   1

1  1   1

EXCLUSIVE DISJUNCTION '!+'

Proposition 'p or q, but not both' is called exclusive proposition. This proposition is denoted as p!+q.

Exclusive disjunction is presented by the following truth table:

p  q  p!+q

0  0    0

0  1    1

1  0    1

1  1    0

IMPLICATION '=>'

If p and q are propositions., than the proposition 'if p than q' is called implication of the proposition q with proposition p, or implication of proposition p to the proposition q. Implication is denoted as p=>q.

Implication p=>q is false if and only if p is true and q is false, i.e. 1=>0.

Truth table is:

p  q  p=>q

0  0    1

0  1    1

1  0    0

1  1    1

EQUIVALENCY '<=>'

If p and q are propositions., than the proposition ' if p than q and if q than p' is called equivalency of proposition p with the proposition q and denotes p<=>q.

Truth table for equivalency is:

p  q  p<=>q

0  0    1

0  1    0

1  0    0

1  1    1

LOGICAL OPERATORS PRIORITY

1. Negation '#'

2. Conjunction '*'

3. Disjunction'+', exclusive disjunction '!+'

4. Implication'=>'

5. Equivalency'<=>'

Note: In this program (LE) precedence of logical operators are changeable.

TAUTOLOGY, CONTRADICTION

Definition 1. Every complex proposition that is formed by applying logical operators '#', '*', '+', '!+', '=>', '<=>' to some initial propositions is called formula.

Definition 2. Formula that gives result  '1' for every combination of truth values of propositions that makes that formula is called tautology.

Definition 3. Formula that gives result  '1' for every combination of truth values of propositions that makes that formula is called contradiction.

PROPERTIES OF LOGICAL OPERATORS

Theorem 1. Conjunction, disjunction and equivalency are commutative:

(p*q)<=>(q*p)

(p+q)<=>(q+p)

(p<=>q)<=>(q<=>p)

Theorem 2. Conjunction, disjunction and equivalency are associative:

((p*q)*r)<=>(p*(q*r))

((p+q)+r)<=>(p+(q+r))

((p<=>q)<=>r)<=>(p<=>(q<=>r))

Theorem 3. Conjunction and disjunction are idempotent:

(p*p)<=>p

(p+p)<=>p

Theorem 4. Conjunction is distributable to disjunction and vice verse:

(p*(q+r))<=>((p*q)+(p*r))

(p+(q*r))<=>((p+q)*(p+r))

Theorem 5. Conjunction is absorbent to disjunction and vice verse:

(p*(p+q))<=>p

(p+(p*q))<=>p

Theorem 6. Negation is involute:

#(#p)<=>p

Theorem 7. De Morganov's laws:

#(p+q)<=>#p*#q

#(p*q)<=>#p+#q

Theorem 8. '1' is neutral element for conjunction and equivalency, and '0' is neutral element for disjunction:

(p*1)<=>(1*p)<=>p

(p<=>1)<=>(1<=>p)<=>p

(p+0)<=>(0+p)<=>p

Theorem 9. '1' is null element for disjunction, and '0' is null element for conjunction:

(p+1)<=>(1+p)<=>1

(p*0)<=>(0*p)<=>0

 

"Linear algebra, polynomials, analytic geometry" - D.S. Mitrinovic, D. Mihailovic, P.M. Vasic Publisher: Building Book Year: 1973

Conjunction

Disjunction

Exclusive disjunction

Implication

Equivalency