Jump to content

User:Wvbailey/Propositional formula

From Wikipedia, the free encyclopedia
< User:Wvbailey
This is an old revision of this page, as edited by Wvbailey (talk | contribs) at 14:31, 30 October 2007 (→System based on truth tables). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Informal development: propositional formulas

Propositions are simple declarative sentences (assertions) that describe the condition of a particular object of sensation: e.g. "This cow is blue", "There's a coyote!" ["That coyote IS]". A long sentence can usually be reworded into a series of these short declarative sentences, although the result may sound stilted. Each unique proposition (sentence, assertion) can then be assigned a variable.

Example: "If I have some food and its noon and it's not raining then we are going on a picnic, but if it is raining then we eat at home"

"I have some food" = f; "It's noon" = n; "It is raining" = r, "We are going on a picnic" = p, "We eat at home" = h.

These variables are linked by the sentential connectives (also called logical connectives, operators, logic gates). The connectives derive their intuitive meanings from their use in common language. The most common ones are NOT ( ~, ￢, negation), OR ( V disjunction: inclusive-or: "a" or "b" or both simultaneously), AND ( &, ⋀, conjuction, also "but"), and IF ... THEN ... ( →[[implication: "a IMPLIES b").

(((f & n & r) → p) & (r → h ))

Mathematical logic adds EQUIVALENCE, ( ←→, IFF: "If and only if"). Electrical engineering creates specific operator-symbols for NOT, AND, and OR and adds NOR (NOT and OR followed by NOT), NAND (AND followed by NOT; also called "the stroke" | ), XOR (eXclusive-OR: a or b but not both, "not-equivalent", "addition without carry"). Computer science adds the CASE operator also used by engineering (IF-THEN-ELSE).

Once a "proposition" (sentence) has been converted into a propositional formula, the formula can be manipulated by use of an algebra not too different from arithmetic. An algebra (i) generalizes formulas by use of variables to represent constants (numbers), (ii) presents rules for creating formulas from formulas, (iii) presents rules for simplifying formulas, (iv) presents rules for the evaluation of a formula. The propositional algebra closely resembles an arithmetic that starts with three rules symbolized by + , ∙, and 1-, variables (e.g. a, b, c ... x, y, z,...), two constants 0, 1, the equate-symbol =, and parentheses ( , ) . But unlike conventional arithmetic, only one of two values are assigned to any variable and to the outcome of an operation[ref> Engineering sometimes uses the + and ∙ when no confusion can result.</ref>. Because only 0 or 1 can result from an operation, there is no "carry" for addition. So a choice has to be made: either 1 + 1 = 1 (OR) or 1 + 1 = 0 (exclusive-or, XOR).

Because confusion will likely result from the use of +, ∙ and 1-, the algebra of propositions adopts different symbols:

Arithmetic concept Arithmetic symbol Propositional (sentential-logic) connective Logic symbols Alternate logic symbols Venn diagram concept Example: Boolean arithmetic Example: Propositional evaluations
sum + OR V disjunction (0+0) = 0, (0+1) = 1, (1+0) = 0, (1+1) = 1 (0 V 0) = 0, (0 V 1) = 1, (1 V 0) = 1, (1 V 1) = 1
product ∙ AND ⋀ & conjunction (0∙0) = 0, (0∙1) = 0, (1∙0) = 0, (1∙1) = 1 (0 ⋀ 0) = 0, (0 ⋀ 1) = 0, (1 ⋀ 0) = 1, (1 ⋀ 1) = 1
difference 1- NOT ￢ ~ negation (1 -(1))=0, (1- (0)) =1 ￢(1)=0, ￢(0)=1

The "laws" of propositional calculus: The distributive law, associative law, and commutative laws apply with one MAJOR exception: a distributive law exists for + over ∙ (!).

Algebraic laws Algebra formulas Boolean formulas Propositional formulas
Commutation ( a + b ) = ( b + a ) ( a + b ) = ( b + a ) ( a V b ) = ( b V a )
Commutation ( a ∙ b ) = ( b ∙ a ) ( a ∙ b ) = ( b ∙ a ) ( a & b ) = ( b & a )
Association ((a+b)+c) =( (a+(b+c)) ((a+b)+c) =( (a+(b+c)) ((a V b) V c) = (a V (b V c) )
Association ( (a∙b)∙c) = (a∙(b∙c) ) ( (a∙b)∙c) = (a∙(b∙c) ) ((a & b) & c) = (a & (b & c) )
a+(b∙c) = (a+b) ∙ (a+c) a V (b & c) = (a V b) & (a V c) Distribution of OR over AND
Distribution a∙(b+c) = (a∙b) + (a∙c) a∙(b+c) = (a∙b) + (a∙c) a & (b V c) = (a & b) V (a & c)

Other common connectives: The other connectives are usually defined in terms of the three simple connectives NOT, OR, AND:

IMPLY: ((~(a) V (a)) ≡ ((a) → (b))
BICONDITIONAL or LOGICAL EQUIVALENCE: (a ←→ b) ≡ ( (a & b) V ( ~(a) & ~(b) )

Logical implication does not behave according to the commutative or distributive, associative or rules listed above.

Synthesis and Analysis: One process for synthesis creates a propositional formula from a truth table that is laid down according to a specification. Another approach uses following "theorems" and the notion of substitution to create as complex a formula as desired (cf McClusky 1965:85):

  • (x V 0) = x (Identity)
  • (x & 1) = x (Identity)
  • (x & ~(x)) = 0 (Complements)
  • (x V ~(x)) = 1 (Complements, (x → x) )
  • ~(~(x)) = x (Involution, double negation)
Example: Start with proposition "a". Equate (a V 0) = a. Substitute (b & ~(b))=0 for 0: (a V (b & ~(b)))=a. Distribute "a V" across (b & ~(b)): (a V b) & (a V ~(b) ) = a. Observe that (a V ~(b)) = (~(b) V a) ≡ (b → a). Likewise observe that (a V b) = (b V a) and b = ~(~(b)) so (b V a) = (~(~b)) V a) ≡ (~(b) → a). Put both of these back into the equivalence: (~(b) → a) & (b → a) = a.
= a
b a ( ( ( ~ (b) → a) & (b → a) ) = a
0 0 1 0 0 0 0 0 1 0 1 0
0 1 1 0 1 1 1 0 1 1 1 1
1 0 0 1 1 0 0 1 0 0 1 0
1 1 0 1 1 1 1 1 1 1 1 1


Quite often, if a particular place in the table is unimportant the table's designer uses a third symbol "d" ("don't care") for added flexibility.

Analysis is the opposite process whereby, when given a propositional formula, the truth table and perhaps a Karnaugh map are created from the table. The above theorems also


Reduction: Both synthesis and analysis quite often lead to reduction or simplification of the formula, or its conversion to what is known as disjunctive normal form ( or less commonly, conjunctive normal form. A number of tools (methods, algorithms) are available to do this.

Besides the theorems above, The single most important of DeMorgan's theorem is the following (cf McClusky p. 87, PM p. 119-120):

(a & b & ... & z) = ~(~a V ~b V ... V ~z)
(a V b V ... V z) = ~(~a & ~b & ... & ~z)

Formal development

The topic presupposes a philosophy of the nature of sensations of objectsand and their being (i.e. ontology ). The synthesis (creation) and analysis of propositional formulas appear in philosophy, mathematics, and electrical engineering. Contributions to the art have come from all three disciplines.

Historical development

Bertrand Russell (1912:74) lists three laws of thought that derive from Aristotle: (1) The law of identity: "Whatever is, is.", (2) The law of contradiction: "Nothing cannot both be and not be", and (3) The law of excluded middle: "Everything must be or not be."

Example: Here O is an expression about an objects BEING or QUALITY:
(1) O = O; (2) ~(O & ~O); (3) (O & ~O)

The use of the word "everything" in the law of excluded middle renders Russell's expression of this law open to debate. If it is restricted to an expression about BEING or QUALITY with reference to a finite collection of objects (a finite "universe of discourse") then an assertion such as: "This object must either BE or NOT BE (in the collection)", or "This object must either have this quality or not have this quality (relative to the objects in the collection)" is considered acceptable. See more at Venn diagram.

Although a propositional calculus originated with Aristotle, the notion of an algebra applied to propositions had to wait until the early 1800's. In an (adverse) reaction to the 2000 year tradition of Aristotle's syllogisms, John Locke's Essay concerning human understanding (1690) used the word semiotics (theory of the use of symbols). By 1826 Richard Whately had critically analyzed the syllogistic logic with a sympathy torward Locke's semiotics. George Bentham's work (1827) resulted in the notion of "quantification of the predicate" (1827) (nowdays symbolized as ∀ ≡ "for all"). A "row" instigated by William Hamilton over a priority dispute with De Morgan "inspired George Boole to write up his ideas on logic, and to publish them as MAL [Mathematical Analysis of Logic] in 1847" (Grattin-Guinness and Bornet 1997:xxviii).

About his contribution Grattin-Guinness and Bornet comment:

"Boole's principal single innovation was [the] law (6.3)2 (i.e. xn = x) for logic: it stated that the mental acts of choosing the property x and choosing x again and again is the same as choosing x once... As consequence of it he formed the equations x•(1-x)=0 and x+(1-x)=1 which for him expressed respectively the law of contradiction and the law of excluded middle." For Boole "1" was the universe of discourse and "0" was nothing. (p. xxviiff)

Frege's massive undertaking resulted in a formal calculus of propositions, but his symbolism is so daunting that it had little influence excepting on one person: Bertrand Russell. First as the student of Alfred North Whitehead he studied the Frege's work and made a (famous, notorious) ememdation with respect to it (1904). This work led to a collatoration with Whitehead that, in the year 1912, produced the first volume of Principia Mathematica. It is here that, what we consider "modern" propositional logic, first appeared. In particular, PM introduces the notions of NOT and OR and the assertion symbol ⊦ as primitives. In terms of these notions they defined IMPLICATION → ( def. *1.01: ~p V q ), then AND (def. *3.01: ~(~p V ~q) ), then EQUIVALENCE p ←→ q (*4.01: (p → q) & ( q → p ) ).

Computation and switching logic:

Example: Given binary bits ai and bi and carry_ini their summation Σi and carry_outi are:
  • ( ( ai XOR bi ) XOR carry_ini )= Σi
  • ( ai & bi ) V carry_ini ) = carry_outi;

Propositions

For the following, propositions are simple declarative utterances that do not involve the use of words "all", "some", ambigous "the" etc. [ref> PM p. 91 singles out "the" because they are requiring a clear-cut "object of sensation"; they stipulate the use of "this" (p. 91)</ref>. Thus the simple "primitive" assertions must be about specific objects or specific states of mind. Each must have at least a noun (an immediate object of thought or observation) a verb, and perhaps an adjective or adverb. "Dog!" probably implies "I see a dog" but is ambiguous and should be rejected. Properly-phrased propostions (assertions) are the following: "This squirrel is dead", "This dog runs", "My cow (that one right there!) is blue", "I think of Jeannie", "Switch M31 is closed", "This cap is off", "Tomorrow is Friday", "The assertion: 'This statement is false' is false", etc.

Testimony: If I assert that "I am undecided about whether or not my cow is blue" or perhaps "My cow is an indeterminate shade of blue" both of these assertions are as much about my state of mind as they are about the cow -- I may be hallucinating and no cow is to be observed by witnesses, let alone a blue cow. However, if witnessed the utterances become objects, and that they were uttered is also a truth. Furthermore unless I am proved to be lying, they have to be accepted as "truths" as far as they are my beliefs. Further investigations re required to see if in fact (i) a cow exists where I am pointing, (ii) the cow is bluish or not.

Logical connectives

NOT: In all cases a system of symbols must, either directly or indirectly, include one for NOT -- a binary relation ( a, b ), i.e. an "input" "a" and output "b".

The fundamental notion of "NOT" derives from the law of contradiction: Our intuition (that is, our knowing based upon repeated observation and inductive reasoning ) is unwilling to accept simultaneous assertions of BEING (Dog!) and NOT-BEING (Not-dog!), or asseertions of QUALITY (blue) and NOT-QUALITY (not-blue), when applied to the same object simultaneously in place and time. We say these notions are contradictory. Russell (1912) believed, in the manner of the rationalists, this knowing to be "self-evident" i.e. derived from a priori (intrinsic, built-in) awareness; the empiricists such as Locke and Hume disagreed.

Example: If this morning I look out my window and observe something in my field and utter: "That cow is blue!", then , I am not allowed to go on in the same breath assert: "That cow is not blue!". Difficulties will arrise if I assert "That cow is blue", and my wife asserts: "That cow is not blue!".

If for some reason, such as the consequence of an analysis or investigation, both assertions about an object exist in a place and time, then the observations are said to be inconsistent.

Example: My assertion: "That cow is blue" and my wife's assertion "That cow is not blue!" are inconsistent assertions.

AND, OR: At least one ternary relation ((a, b), c) is required if we are to combine two propositions, each with their own truth or falsity, into the single assertion with a single truth or falsity.[ref> Both NOT and AND can be combined into a single connective such as NAND ( NOT "a AND b" )) but the resulting formulas are unwieldy. Ditto for NOT and OR.</ref> As noted above, as algebraic operators these both behave according to the commutative law, i.e. (&(f, p), e) = (&(p, f), e). AND carries the intuitive notion of "simultaneity" between two propositions: "Switch #1 is closed" AND "Switch #2 is closed" at the same time. OR, on the other hand, carries with it a "looser" notion of "just one or the other is ..."

Example: "I have food" AND "I am going on a picnic." f = "I have food", p = "I am going on a picnic": (f & p)=e. Given this conjunction of events I am probably going to eat.


IF ... THEN ...: This operator does not behave according to the commutative law. Thus (→(f, p), e) ≠ (→(p, f), e). In spoken language it also contributes a sense of causality.

Example: IF "I have food" THEN "I am going on a picnic": (f → p) = e

Common usage seems to expect that, at least indirectly, "my having food" is a causitive factor in my "going-on-a-picnic" behavior. But in the propositional logic this is not the case: "IF "f" THEN "p" " is just formally defined as NOT-"f" OR "p" (~(f) V p ). As this is not common to speech this operator can be confusing. It is not used in electrical engineering.

Example: "It's not the case that 'I have food'" OR "I am going on a picnic": ~(f) V p

IF ... THEN ... ELSE: This operator appears in computer science as the simplest CASE operator and in electrical engineering as the AND-OR-SELECT operator. It is a 4-ary relation: (CASE(b,a),c), d). Although it sounds like two implications it is not.

Example: IF "I have food" THEN "I am going on a picnic" ELSE (otherwise) "I am taking a nap." = ( "I have food" AND "I am going on a picnic" ) OR ( "Its not the case that 'I have food'" AND "I am taking a nap." )
"I have food" = f, "I am going on a picnic" = p, "I am taking a nap" = n:
("f" AND "p") OR ( NOT-"f" AND "n"): (f & p) V (~(f) & a)

Logical EQUIVALENCE: This is not the notion of identity! In the example, "Going on a picnic" is not identical to "having food"; "having food" is identical to "having food", for example. But the two are "equivalent". In the following the first condition is called the NECESSARY condition, and the converse is called the SUFFICIENT condition. Conjoined by AND they are said to be NECESSARY and SUFFICIENT and thus EQUIVALENT.

Example: (IF "I have food" THEN "I am going on a picnic") & (IF "I am going on a picnic" THEN "I have food").


Formal development of propositional formulas

At least two possible approaches to the development of a propositional calculus: (1) Definition by truth tables and (ii) a set of axioms (cf Tarski 1941:146-147).

System based on truth tables

File:Propositional formula 1.JPG
The input variables p, c, d can represent any three propositions. The other, intermediate variables u, v, and w are for purposes of substitution. The symbols shown are typical to much engineering documentation, but other symbols are used as well. Usually a little circle represents "inversion" (NOT). For example, and AND gate with a little circle drawn at its output becomes a NAND; an OR with a little circle drawn at its output is a NOR.

Truth table definitions: The following are to be regarded as definitions. As only 16 tables (24) are possible, the choice of symbolization is necessarily limited.

variable variable NOT NOT AND OR variable variable NOT NOT AND OR variable variable NOT NOT AND OR
b a ~(b) ~(a) (b & a) (b V a) b a ~(b) ~(a) (b & a) (b V a) b a ~(b) ~(a) (b & a) (b V a)
※ ※ ℥ ℥ ※ ※ 0 0 1 1 0 0 F F T T F F
※ ℥ ℥ ※ ※ ℥ 0 1 1 0 0 1 F T T F F T
℥ ※ ※ ℥ ※ ℥ 1 0 0 1 0 1 T F F T F T
℥ ℥ ※ ※ ℥ ℥ 1 1 0 0 1 1 T T F F T T


Engineering-symbol formation rules: A typical treatment used by engineers employs diagrams made from one-input NOT (inverter) symbols, and 2 input AND, OR, NOT, NOR, XOR and AND-OR-SELECT operator-symbols. These are linked by lines to indicate substitution. The recommended procedure is to start at the top or right with a labelling of the input-variables. Assign variable names to each operator's output (e.g. u, v, w in the drawing). Start at the top and connect the inputs to their operators. Connect the outputs of the operators to operators further down the line. Make appropriate substitutions starting at the top to derive the final formula(s) at the bottom (e.g. q in the drawing).

Evaluation of formulas: Any two pairings of symbols is possible, for example: { ℥, ※ } , { T, F }, { 1, 0 ), { ON, OFF }, { |, O, }, { open, closed }, { up, down }, { +5 volts, 0 volts } etc. The usual process is to "map" (put into 1-1 correspondence) definitions such as { door_open = +5 volts, door_closed = 0 volts } to { 1, 0 }.

Caution is advised. It is quite common to reverse the "sense" of the values even in the same system. For example, switches come in two varieties: normally-open and normally-closed. So a system of two switches might invert the evaluation of one of the switches based upon behavior in the circuit: { { switch_#1_active = +5 volts at node B17, switch_#1_inactive = 0 volts node B17, }, { switch_#2_active = 0 volts at node B18, switch_#2_inactive = +5 volts node B18 } }. Also, { T, F } should be reserved for abbreviations having to do with "Truth" and "Falsehood".

Axiomatic system

Start with a finite collection of objects and then define relationships between the objects. In this way, define more objects called formulas whose "properties hold by virtue of "form" alone, regardless of "content"" (B-B-J p. 101). In the second part valuation, assign the variables "values" and evaluate the resulting formulas.

Non-axiomatic sign: Defined as: ≡ (is identical to by definition).

variables: letters {a, b, ... z, ...},
connective-symbols: ~ (NOT), & (AND), V (OR)
Predicate symbol: = (equates, is the same as, used for assignment of a name to a formula)
parentheses: ), (

Concatenation-formation rules: A mathematical treatment usually proceeds by concatenation of symbols into a "symbol string".

Example: ))&~(ab))V) is a string of symbols (This string is not well-formed per the process to be described below.)

The rules that dictate what is and is not a well-formed formula are, alternately called "the grammar", or "the syntax". The rules must be absolutely mechanical and must leave no chance for ambiguity. They proceed by an induction process that begins with a basis (i) and is followed by formation rule (ii). A third rule -- substitution -- is also required in this system.

The following system -- based on the objects ~(a)=vi and (a R2 b)=vi -- is an example and by no means the only possible system. Another system can be based upon objects vi=R1(a) and vi=R2(a, b) where R1 is a binary relation e.g. the ordered-pair (a,c), and R2 is a ternary relation, i.e. ((a,b), d).

Formula:

  • (i) If s is a variable then (s)=s is a formula;
  • (ii) if vi is a variable and s and t are formulas then ~(s)=vi is a formula, then (s V t)=vi, (s & t)=vi, (s → t)=vi, (s ←→ t)=vi are formulas.
  • (iii) The only formulas are those given by rules (i) and (ii).

Substitution rule: Substitution is the method by which one plugs a constant or a formula inside a formula in place of a variable. The rule is: Throughout the formula, wherever the variable-to-be-substituted is found, the substitution of the formula or constant for the variable must take place.

Axioms (Huntington 1908, Suppes 1957):

  • 0 E(a)E(b) a ≠ b
  • 1 (a V 0) = a
  • 2 (a & 1) = a
  • 3 (a V b) = (b V a)
  • 4 (a & b) = (b & a)
  • 5 (a & (b V c) = ((a & b) V (a & c))
  • 6 (a V (b & c) = ((a V b) & (a V c))
  • 7 (a V ~a) = 1
  • 8 (a & ~a) = 0

Major theorems derived from this set of axioms:

  • 9 (a V a) = a
  • 10 (a & a) = a
  • 11 ~(~a) = a
  • 18 ((q & b) & c) = (a & (b & c))
  • 19 ((a V b) V c) = (a V (b V c))

Example: Derive formula #9:

Start with 1: (a V 0) = a
Substitute 7 into 1: (a V (a & ~a)) = a
Apply 5: ((a V a) & (a V ~a)) = a
Per 7 ubstitute 1 for (a V ~a): ((a V a) & 1) = a
consider (a V a) a formula named u; per 2: (u & 1) = u; therefore (a V a) & 1 = (a V a) = a. Q.E.D.

Substitution example

The following example works for either system. Given the collection of formulas derived from either speech (example: c = "It's noon", d = "It's a nice day", p = "I have food", q = "We're going picnicking" ) or from engineering (example: c = "Clock-signal is active", d = "Motor-start switch is closed", p = "Motor-TEMP okay", q = "Power is ON to motor" ) the following set of simple formulas will be used to derive a final formula q:

{ ~(d) = u, (c & d) = s, (c & u ) = r, ~(r) = v, (p & v) = q, (s V w) = q }
Substitute ~(d)=u for u in (c & u): (c & ~(d))=r.
Substitute (c & ~(d))=r for r in ~(r)=v: ~((c & ~(d)))=v
Substitute ~((c & ~(d))=v for v in (p & v): (p & ~((c & ~(d)))) = w.
Substitute (p & ~((c & ~(d))))=w for w in (s V w): (s V (p & ~((c & ~(d))))) = q
Substitute (c & d)=s in for s in (s V (p & ~((c & ~(d))))) = q:
((c & d) V (p & ~((c & ~(d))))) = q


Well-formed formula (wff)

Some observations are possible about a well-formed formula assembled per a grammar such as one described above.[ref> Enderton sketches an algorithm that constructs an upside-down tree with the formula at the root; its leaves will be the variables in the formula, e.g. (c, d, q, c, d) and these leaves point upward to the first connectives, etc. (Enderton 2002:17 and 29ff).</ref> (i) The left end is enclosed in a (, the right end by a ) followed by =, (ii) The parentheses come in pairs, and (iii) there is an equal number of left ( and right ) parentheses. With respect to the other symbols, ~s, ~&, ~V, &&, &V, VV, V&, &s, Vs are not allowed ("s" is any variable).

Example: A simple parenthesis checker (does not test for errors such as " ~V " and is easily fooled) starts at the left end of the symbol string and sets a counter to 0. If the left-most symbol is not ( then error else add 1 to counter and continue. Proceed to the right, ignoring all symbols but ( and ); add 1 each time a ( occurs, and subtract 1 if ) occurs. If the count goes to 0, check to see that an = sign is the next symbol to the right else error.

This method locates the "deepest-in" pair(s) of parentheses. It also locates the principal (outermost) connective, V in this example, which has a count of 1 (the same count as the outer parentheses).

Example:

( ( c & d ) V ( q & ~ ( c & ~ ( d ) ) ) ) = q2
count 0 1 2 2 2 2 1 1 2 2 2 2 3 3 3 3 4 4 3 2 1 0 0

Evaluating a wff

An evaluation in a deductive system assigns "values" to the variables (the propositions). In n-ary (e.g. ternary or 3-symbol) systems v variables will create tables with nv rows.

Binary (two-symbol) evaluations

Either a small set of axioms can be used to define the behavior of the symbols, or truth tables for each symbol can be used.

Axioms based on NOT and OR

  • Axiom: a = a
  • Axiom: ~(1) = 0
  • Axiom: ~(0) = 1
  • Axiom: (a V a) = a ; thus (0 V 0) = 0, (1 V 1) = 1
  • Axiom: (~(a) V a) = 1 ; thus (~(0) V 0) = 1, (~(1) V 1) = 1
  • Definition: ( a & b ) ≡ ~(~(a) V ~(b))
  • Definition: ( a → b ) ≡ (~(a) V b)

Axioms based on NOT and AND

  • Axiom: a = a
  • Axiom: ~(T) = F
  • Axiom: ~(F) = T
  • Axiom: (a & a) = a ; thus (T & T) = T, (F & F) = F
  • Axiom: ~(~(a) & a) = 1 ; thus ~(~(0) & 0) = 1, ~(~(1) & 1) = 1
  • Definition: ( a V b ) ≡ ~(~(a) & ~(b))
  • Definition: ( a → b ) ≡ (~(a) V b)

Axioms based on truth table definitions

In a binary (i.e. two-symbol) evaluation, any two unique symbols can work. In general, v variables create tables with 2v rows. If a value is not known in a binary evaluation, it may be written as "u" or if not important, as "d" (don't care); but a truth table is still required with a full assignment of all combinations of variable-value assignments.

The primitive notion of NOT results in the two axioms ~※ ≡ ℥, and ~℥ ≡ ※ that indicate that only two symbols will be allowed in the system. 16 operators (connectives) with 2 symbols as input and one output are possible:

0 1 2 3 4 5 6 7 ~7 ~6 ~5 ~4 ~3 ~2 ~1 ~0
incompatibility (a "+" b) equivalence tautology
(a NOR b) NOT(a) (a XOR b) (a NAND b) (a AND b) (a XNOR b) (a) (a IMPLIES b) (b) (b IMPLIES a) (a OR b)
a b ~(a V b) ~(b) ~(a) (a ⊕ b) b) (a & b) ~(a ⊕ b) (a) (a → b) (b) (a V b)
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
(~a & a) ~(~a & a)

Evaluation: The first thing one needs is values i.e. constants for the variables. If they are known, these constants (e.g. T or F, or 1 or 0) are substituted for their variables one after another until all variables are accounted for. If a variable has no value, the formula is indeterminate. But the formula can be repeated and T plugged into the first formula and F plugged into the second formula and thereby produce both evaluations. In the extreme, where all 2n combinations of n variables are presented in one table, this is the method of truth tables.

Evaluation procedes by finding the "inner-most" [term(s), expression(s)] and evaluating it (or them) from e.g. left to right if there are more than one. Given the evaluation, the new inner-most [term](s) must be again found by a process similar to the parenthesis checker and evaluated. This process is repeated until the last evaluation is complete.

Example: Given that (p, d, c) = (1, 1, 0) and the formula ((c & d) V (p & ~((c & ~(d)))))=q, find the value of q:
  • Plug in all the constants for their variables: ((0 & 1) V (1 & ~((0 & ~(1)))))=q
As found by the parenthesis algorithm, the innermost formula is u = ~(d) = ~(1) = 0
((0 & 1) V (1 & ~((0 & 0))))=q
  • As found by a 2nd application of the parenthesis algorithm, the innermost formula now is r=(0 & 0)= 0
((0 & 1) V (1 & ~((0))))=q
  • As found by a 3rd application of the parenthesis algorithm, the innermost formula is (0) = 0:
((0 & 1) V (1 & ~(0)))=q
  • As found by a 4rd application of the parenthesis algorithm, the innermost formula is ~(0) = 1:
((0 & 1) V (1 & 1))=q
  • As found by a 5th application of the parenthesis algorithm, there are two innermost formulas. Start with the one on the left: (0 & 1)=0
(0 V (1 & 1))=q
  • Evaluate the formula on the right: (1 & 1) = 1
(0 V 1)=q
  • 6th application of the parenthesis algorithm locates (0 V 1) = 1; this ends the evaluation.
1=q
Step: Description: s q w v r u
1 Start with known wff ( ( c & d ) V ( p & ~ ( ( c & ~ ( d ) ) ) ) ) = q
2 Plug in values for variables ( ( 0 & 1 ) V ( 1 & ~ ( ( 0 & ~ ( 1 ) ) ) ) ) = q
3a count parentheses count 0 1 2 2 2 2 1 1 2 2 2 2 3 4 4 4 4 5 5 4 3 2 1 0 0
3b Find deepest formula e.g. u = ~(d) = ~(1): ( ( 0 & 1 ) V ( 1 & ~ ( ( 0 & ~ ( 1 ) ) ) ) ) = q
3c Evaluate "deepest formula" e.g. u = 0: 0
4a Count parentheses: count 0 1 2 2 2 2 1 1 2 2 2 2 3 4 4 4 4 3 2 1 0 0
4b Find new "deepest formula": ( ( 0 & 1 ) V ( 1 & ~ ( ( 0 & 0 ) ) ) ) = q
4c Evaluate new "deepest formula": 0
5a Count parentheses: count 0 1 2 2 2 2 1 1 2 2 2 2 3 3 2 1 0 0
5b Find new "deepest formula": ( ( 0 & 1 ) V ( 1 & ~ ( 0 ) ) ) = q
5c Evaluate new "deepest formula": 0
6a Count parentheses: count 0 1 2 2 2 2 1 1 2 2 2 2 3 3 2 1 0 0
6b Find new "deepest formula": ( ( 0 & 1 ) V ( 1 & ~ ( 0 ) ) ) = q
6c Evaluate new "deepest formula": 1
7a Count parentheses: count 0 1 2 2 2 2 1 1 2 2 2 2 1 0 0
7b Find new "deepest formula": ( ( 0 & 1 ) V ( 1 & 1 ) ) = q
7c Evaluate new "deepest formula": 0
8a Count parentheses: count 0 1 1 1 2 2 2 2 1 0 0
8b Find new "deepest formula": ( 0 V ( 1 & 1 ) ) = q
8c Evaluate new "deepest formula": 1
9a Count parentheses: count 0 1 1 1 1 0
9b Find new "deepest formula": ( 0 V 1 ) = q
9c Evaluate new "deepest formula": 1 = q

The above example is evaluated in the 6th row of the truth-table shown below.

Truth table-analysis: A truth table is just a generalization of the above example. It creates 2n rows, one for each unique combination of variable-values, where n is the number of variables:

TEMP okay switch closed clock active motor ON
food nice day noon picnic
s q w v r u
row p d c ( ( c & d ) V ( p & ~ ( c & ~ ( d ) ) ) )
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
1 0 0 1 1 0 0 0 0 0 0 1 1 1 0
2 0 1 0 0 0 1 0 0 0 1 0 0 0 1
3 0 1 1 1 1 1 1 0 0 1 1 0 0 1
4 1 0 0 0 0 0 1 1 1 1 0 0 1 0
5 1 0 1 1 0 0 0 1 0 0 1 1 1 0
6 1 1 0 0 0 1 1 1 1 1 0 0 0 1
7 1 1 1 0 1 1 1 1 1 1 1 0 0 1

Reduction to normal form

> Requires some tools: truth table and indirectly Hasse diagram, and Karnaugh map.

> Karnaugh map: for small number of variables (6 or less) the use of Karnaugh maps. A Karnaugh map is a flattened (i.e. 2-dimensional) Hasse diagram.

Literal, term and alterm

In electrical engineering a variable v or its negation ~(v) is lumped together into a single notion called a literal. A string of literals connected by AND is called a term. A string of literals connected by OR is called an alterm. Typically the literal ~(v) is abbreviated ~v.

Example: a, b, c, d are variables. ((( a & ~(b) ) & ~(c)) & d) is a term. This can be abbreviated as (a & ~b & ~c & d).
Example: p, q, r, s are variables. (((p & ~(q) ) & r) & ~(s) ) is an alterm. This can be abbreviated as (p V ~q V r V ~s).

minterms

In the same way that a 2n-row truth table displays the valuation of a propositiional formula for all 2n, n variables produces a 2n-square Karnaugh map (even though we cannot draw it). For example, 3 variables produces 23 = 8 squares ; each of corresponding truth-table row and Karnaugh-map square represents one minterm. Thus 4 variables produces 16 rows and 16 squares, and thus 16 minterms. Any propositional formula can be reduced to a "logical sum" (OR) of the active (i.e. "1"- or "T"-valued) minterms. When in this form the formula is said to be in disjunctive normal form.

In the following table, observe the peculiar sequence of rows: (0, 1, 3, 2, 6, 7, 5, 4, 0). the first column is the decimal equivalent of the binary equivalent of the digits cba,

Example: cba2 = c*22 + b*21 + a*20:
cba = (c=1, b=0, a=0) = 1012 = 1*22 + 0*21 + 1*20 = 510

This sequence comes about because in each row, only one variable changes at a time. Gray code is derived from this notion. It can be extended to renderings of three and four-dimensional objects called Hasse diagrams. Hasse diagrams flattened into two dimensions these are Karnaugh maps.

decimal equivalent of (c, b, a) c b a minterm
0 0 0 0 (~c & ~b & ~a)
1 0 0 1 (~c & ~b & a)
3 0 1 1 (~c & b & a)
2 0 1 0 (~c & b & ~a)
6 1 1 0 (c & b & ~a)
7 1 1 1 (c & b & a)
5 1 0 1 (c & ~b & a)
4 1 0 0 (c & ~b & ~a)
0 0 0 0 (~a & ~b & ~c)


Complex formulas such as those for binary adders typically begin with a stage that decode the input binary code into its minterms. Any propositional formula can be reduced to its conjuctive normal form.

Reduction by use of the Map method (Veitch, Karnaugh)

  • Produce the formula's truth table. Number its rows using the binary-equivalents of the variables (usually just sequentially 0 through n-1) for n variables.
  • Draw a Karnaugh map and number its squares per its convention.
  • For all rows of the truth table, wherever a "T" or "1" appears in the output (e.g. q = 1), put a 1 in the corresponding square of the Karnaugh map; else put a "0" in the square when the row's output is 0 (e.g. q = 0).
Technically, the propositional function has been reduced to its (unminimized) conjunctive normal form: each square has its minterm expression and these can be OR'd to produce the formula in its (unminimized) conjunctive normal form.
  • In minterms of adjacent (abutting) 1-squares (T-squares) the number of their literals can be reduced. Two abutting squares loose one literal, four squares in a rectangle or square loose two literals, eight squares in a rectangle loose 3 literals, etc. (One seeks out the largest square or rectangles.) This process continues until all abutting squares are accounted for, at which point the propositional formula is said to be minimized.

Multiple-output reductions: Prime implicant method (McCluskey, Shorr)

Propositional formula with "feedback"

The following illustrates what happens when a formula derives one of its inputs “p” from its output “q”. Unless otherwise expressly forbidden, no stipulation within the theory [system of objects and relations] forbids this from happening.

Example: ( ( c & d ) V ( p & ( ~( d ) & ~( c ) ) ) ) = q, but now let p = q
( ( c & d ) V ( q & ( ~( d ) & ~( c ) ) ) ) = q

Two conditions can result: (1) oscillation, (2) memory (1) Oscillation: Without the notion of “delay”, this condition presents itself as undecidability; neither { T, F }, ( or { ON, OFF }, { 1, 0 }, etc) can be determined. With delay (time-delay in the process of ) the condition presents itself as alternating values e.g. 1010101010..., ad infinitum. (2) Memory: Without the notion of “delay”, this condition presents itself as inconsistency between the fed-back output variable q2 is acting as an input (e.g. q = q2).

The following shows that, when q is considered to be the same as q2, that the formula, observed from the “outside looking in”, when c=0 and d=0 the output q can be either 1 or 0. Without knowledge of what is going on “inside” the formula, this represents a condition of [randomness]. That is, sometimes when we look at q we see 0 and other times 1.

To understand [predict] the behavior of this formula requires a different theory and the more sophisticated analyusis of sequential circuits. Thus propositional formulas with feedback lead, in their simplest form, to state machines; they lead to memories in the form of Turing tapes and counter-machine counters. From combinations of these elements one can build any sort of bounded computational model (e.g. Turing machines, counter machines, register machines, Macintosh computers, etc).

Retrieved from "https://en.wikipedia.org/w/index.php?title=User:Wvbailey/Propositional_formula&oldid=168082860"