Editing Propositional formula (section)

== Well-formed formulas (wffs) ==
A key property of formulas is that they can be uniquely parsed to determine the structure of the formula in terms of its propositional variables and logical connectives. When formulas are written in [[infix notation]], as above, unique readability is ensured through an appropriate use of parentheses in the definition of formulas. Alternatively, formulas can be written in [[Polish notation]] or [[reverse Polish notation]], eliminating the need for parentheses altogether.

The inductive definition of infix formulas in the previous section can be converted to a [[formal grammar]] in [[Backus-Naur form]]:

<syntaxhighlight lang="bnf">
<formula> ::= <propositional variable>
| ( ¬ <formula> )
| ( <formula> ∧ <formula>)
| ( <formula> ∨ <formula> )
| ( <formula> → <formula> )
| ( <formula> ↔ <formula> )
</syntaxhighlight>
It can be shown that any expression matched by the grammar has a balanced number of left and right parentheses, and any nonempty initial segment of a formula has more left than right parentheses.<ref>cf Minsky 1967:75, section 4.2.3 "The method of parenthesis counting". Minsky presents a state machine that will do the job, and by use of induction (recursive definition) Minsky proves the "method" and presents a theorem as the result. A fully generalized "parenthesis grammar" requires an infinite state machine (e.g. a Turing machine) to do the counting.</ref> This fact can be used to give an algorithm for parsing formulas. For example, suppose that an expression ''x'' begins with <math>( \lnot</math>. Starting after the second symbol, match the shortest subexpression ''y'' of ''x'' that has balanced parentheses. If ''x'' is a formula, there is exactly one symbol left after this expression, this symbol is a closing parenthesis, and ''y'' itself is a formula. This idea can be used to generate a [[recursive descent parser]] for formulas.

'''Example of parenthesis counting''':

This method locates as "1" the '''principal connective''' {{--}} the connective under which the overall evaluation of the formula occurs for the outer-most parentheses (which are often omitted).<ref>Robbin p. 7</ref> It also locates the inner-most connective where one would begin evaluatation of the formula without the use of a truth table, e.g. at "level 6".
{| style="margin-left: auto; margin-right: auto; border: none;"
|- style="font-size:9pt" align="center" valign="bottom"
| width="32.25" Height="12" | 
! width="27.75" | start
|style="background-color:#99FF99" width="12" | (
|style="background-color:#99FF99" width="12" | (
|style="background-color:#99FF99" width="12" | (
| width="12" | c
| width="12" | &
| width="12" | d
|style="background-color:#FFC000" width="12" | )
| width="12" | V
|style="background-color:#99FF99" width="12" | (
| width="12" | p
| width="12" | &
| width="12" | ~
|style="background-color:#99FF99" width="12" | (
|style="background-color:#99FF99" width="12" | (
| width="12" | c
| width="12" | &
| width="12" | ~
|style="background-color:#99FF99" width="12" | (
| width="12" | d
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
| width="12" | = 
|style="background-color:#99FF99" width="12" | (
|style="background-color:#99FF99" width="12" | (
|style="background-color:#99FF99" width="12" | (
| width="12" | c
| width="12" | &
| width="12" | d
|style="background-color:#FFC000" width="12" | )
| width="12" | V
|style="background-color:#99FF99" width="12" | (
| width="12" | p
| width="12" | &
| width="12" | d
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
| width="12" | V
|style="background-color:#99FF99" width="12" | (
| width="12" | p
| width="12" | &
| width="12" | ~
|style="background-color:#99FF99" width="12" | (
| width="12" | c
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|style="background-color:#FFC000" width="12" | )
|- style="font-size:9pt"
! Height="13.5" align="right" valign="bottom" | count
| align="center" valign="bottom" | 0
|style="background-color:#99FF99" align="center" valign="bottom" | 1
|style="background-color:#99FF99" align="center" valign="bottom" | 2
|style="background-color:#99FF99" align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 2
| align="center" valign="bottom" | 2
|style="background-color:#99FF99" align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
|style="background-color:#99FF99" align="center" valign="bottom" | 4
|style="background-color:#99FF99" align="center" valign="bottom" | 5
| align="center" valign="bottom" | 5
| align="center" valign="bottom" | 5
| align="center" valign="bottom" | 5
|style="background-color:#99FF99;font-weight:bold" align="center" valign="bottom" | 6
| align="center" valign="bottom" | 6
|style="background-color:#FFC000" align="center" valign="bottom" | 5
|style="background-color:#FFC000" align="center" valign="bottom" | 4
|style="background-color:#FFC000" align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
|style="background-color:#99FF99" align="center" valign="bottom" | 2
|style="background-color:#99FF99" align="center" valign="bottom" | 3
|style="background-color:#99FF99" align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
|style="background-color:#FFC000" align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
|style="background-color:#99FF99" align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
| align="center" valign="bottom" | 4
|style="background-color:#FFC000" align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 2
| align="center" valign="bottom" | 2
|style="background-color:#99FF99" align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
|style="background-color:#99FF99" align="center" valign="bottom" | 3
| align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 3
|style="background-color:#FFC000" align="center" valign="bottom" | 2
|style="background-color:#FFC000" align="center" valign="bottom" | 1
|style="background-color:#FFC000" align="center" valign="bottom" | 0
|}

=== Well-formed formulas versus valid formulas in inferences ===
The notion of valid argument is usually applied to [[inference]]s in arguments, but arguments reduce to propositional formulas and can be evaluated the same as any other propositional formula. Here a valid inference means: "The formula that represents the inference evaluates to "truth" beneath its principal connective, no matter what truth-values are assigned to its variables", i.e. the formula is a tautology.<ref>cf Reichenbach p. 68 for a more involved discussion: "If the inference is valid and the premises are true, the inference is called ''conclusive''.</ref>
Quite possibly a formula will be ''well-formed'' but not valid. Another way of saying this is: "Being well-formed is ''necessary'' for a formula to be valid but it is not ''sufficient''." The only way to find out if it is ''both'' well-formed ''and'' valid is to submit it to verification with a truth table or by use of the "laws":

* Example 1: What does one make of the following difficult-to-follow assertion? Is it valid? "If it's sunny, but if the frog is croaking then it's not sunny, then it's the same as saying that the frog isn't croaking." Convert this to a propositional formula as follows:
*:: " IF (a AND (IF b THEN NOT-a) THEN NOT-a" where " a " represents "its sunny" and " b " represents "the frog is croaking":
*:: ( ( (a) & ( (b) → ~(a) ) ≡ ~(b) )
*: This is well-formed, but is it ''valid''? In other words, when evaluated will this yield a tautology (all T) beneath the logical-equivalence symbol ≡ ? The answer is NO, it is not valid. However, if reconstructed as an ''implication'' then the argument ''is'' valid.
*: "Saying it's sunny, but if the frog is croaking then it's not sunny, ''implies'' that the frog isn't croaking."
*: Other circumstances may be preventing the frog from croaking: perhaps a crane ate it.
* Example 2 (from Reichenbach via Bertrand Russell):
*: "If pigs have wings, some winged animals are good to eat. Some winged animals are good to eat, so pigs have wings."
*: ( ((a) → (b)) & (b) → (a) ) is well formed, but an invalid argument as shown by the red evaluation under the principal implication:
{|style="margin-left: auto; margin-right: auto; border: none;"
|- style="font-size:9pt" align="center"
| width="18.75" Height="12" | W
| width="18.75" | G
| width="4.5" | 
| width="10.5" | 
| width="10.5" | 
| width="10.5" | 
| width="10.5" | 
| width="16.5" | 
| width="10.5" | 
| width="11.25" | 
| width="16.5" | 
| width="10.5" | 
| width="10.5" | 
|style="background-color:#CCC0DA" width="19.5" | arg
| width="14.25" | 
| width="12" | 
|- style="font-weight:bold" align="center"
|style="font-size:9pt" Height="12.75" | a
|style="font-size:9pt" | b
|style="font-size:9pt" | 
|style="font-size:9pt" | (
|style="font-size:9pt" | (
|style="font-size:9pt" | (
|style="font-size:9pt" | a
|style="background-color:#F2DDDC;font-size:9pt" |  ->
|style="font-size:9pt" | b
|style="font-size:9pt" | )
|style="background-color:#DBE5F1" | &
|style="font-size:9pt" | b
|style="font-size:9pt" | )
|style="background-color:#CCC0DA;font-size:9pt" |  ->
|style="font-size:9pt" | a
|style="font-size:9pt" | )
|- style="font-size:9pt" align="center"
| Height="12" | 0
| 0
| 
| 
| 
| 
| 0
|style="background-color:#F2DDDC" | 1
| 0
| 
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#CCC0DA" | 1
| 0
| 
|- style="font-size:9pt" align="center"
| Height="12" | 0
| 1
| 
| 
| 
| 
| 0
|style="background-color:#F2DDDC" | 1
| 1
| 
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:red" | 0
| 0
| 
|- style="font-size:9pt" align="center"
| Height="12" | 1
| 0
| 
| 
| 
| 
| 1
|style="background-color:#F2DDDC" | 0
| 0
| 
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#CCC0DA" | 1
| 1
| 
|- style="font-size:9pt" align="center"
| Height="12" | 1
| 1
| 
| 
| 
| 
| 1
|style="background-color:#F2DDDC" | 1
| 1
| 
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:#CCC0DA" | 1
| 1
| 
|}