Talk:Propositional formula

Expansion

This article was woefully short, so I am going to work on expanding it. I don't want to repeat all of propositional logic here, but we should be able to give a brief overview of the properties of formulas, mention truth assignments, etc. It will take a few days, and the rough draft I have needs a lot of wikilinks to be added. — Carl (CBM · talk) 00:49, 23 October 2007 (UTC)[reply]

The development has become too unwieldy so I've moved it to User:Wvbailey/Propositional formula: visitors are welcome! Bill Wvbailey 14:11, 29 October 2007 (UTC)[reply]

---

I'm not sure what this means: "The use of symbols { T, F } is discouraged in mathematics because of the possibility of confusion with "Truth" and "Falsity",..." The symbols T and F are usually used in mathematics, since truth and falsity is exactly what they are supposed to represent.

One issue that the content above brings to mind is that this article is just about propositional formulas. It isn't meant to be about all of propositional logic. We can have a few sentences that link to other important concepts, like valuations. Here is a rough list of the things that I think should be included in this article:

Basic inductive definition of propositional formulas in the language with negation and the four binary operators $\land ,\lor ,\to ,\leftrightarrow$ . This is the system most often used in math texts. Not present in current version.
Discussion of how the definition would be extende3d to cover other connectives. Link to Logical connectives
Discussion on parsing and unique readability
Very brief summary style discussion of valuations, just enough to give background for the rest of the article. Link to tautology.
Discussion of normal forms

— Carl (CBM · talk) 15:31, 25 October 2007 (UTC)[reply]

---

We had a conflict edit, so there is a lot more here now. I basically agree with what you've written. I will cut the "brainstorm" to reduce the clutter. I am evolving in the direction you are proposing. I am suffering from some confusions and frustrations: in particular I don't like Enderton's 2002 treatment. I find Kleene's 1952 far better. It seems we should be able to construct a very simple induction-like method of how to construct the formulas. Even Kleene's is too complex because he's constructing an arithmetic+logic system. Kleene has some three little lemmas about parenthesis pairing and nesting etc.

RE {T, F}. Problem is, folks other than mathematicians use propositional formulas. I advise anyone doing so (i.e. creating propositional formulas and then evaluating them) to stay away from T and F. If they are doing rhetoric, then the T & F need to come into play. Kleene also agrees, at least with regards to "metamathematical consistency proofs for the calculus" (1952:125). My practical/engineering experience with {T, F} has been very, very poor. In practice, many folks use "reverse logic" and make a mess of T & F. Also, you cannot "compute" with it using what I would call true Boolean logic, i.e. the logic of Boole: ~a = (1-a), a & B = a * b, a V b = (1 - (1-a)*(1-b)), etc.

RE synthesis versus analysis: both aspects need development

RE parsing, normal forms etc. I agree. A lot needs to be said about such things as ((A & B) & C) = (A & B & C)

RE the "algebra" versus the "valuation": my understanding here is the "algebra" is the substitution rules that I have been trying to "axiomatize" with the inductive definitions, plus the reduction-rules such as De Morgan etc. Plus the notions of "distributive law" and "associative law" etc. .

RE: NOT, OR, AND: I recommend we use NOT, OR, AND and define IMPLY, XOR in terms of these others. My thought was to put in the big table as a summary of the definitions of the operators, and be done with it.

WvbaileyBill

The most common presentation of propositional logic use the classical connectives

\land ,\lor ,\to ,\leftrightarrow ,\lnot

. I think sticking with that convention is fine. In any case the article will discuss how other connectives, that take arbitrary finite numbers of formulas, can be added.

There are quotes above that use the word term. Nowadays that word is usually reserved for certain expression in first order logic; there are no more terms in propositional logic. Everything is a formula. — Carl (CBM · talk) 03:35, 26 October 2007 (UTC)[reply]

RE: "term". I wouldn't have a problem with just using "formula" excepting engineers and computer scientists use the notion "term" for a conjunction of variables, i.e. (p & ~q & r) is a "term". In particular minterms are used in the notion of disjunctive normal form. There is a never-ending set of definitions in engineering such as literal for variable or its inverse, prime implicants etc. It's an alternate universe to mathematics. So perhaps I can define "formula" inductively and then define "term" as an alternate usage for (a & b) or (a & b & ... & z). There's also an alterm used in conjunctive normal form e.g. (a V b V ...V z). Bill Wvbailey 18:06, 26 October 2007 (UTC)[reply]

We can certainly say that term is used in certain fields. But in any case it isn't necessary to define terms in order to merely define formulas. — Carl (CBM · talk) 10:29, 28 October 2007 (UTC)[reply]

I agree. I changed above what I had written before. Bill —Preceding unsigned comment added by Wvbailey (talk • contribs) 15:03, 28 October 2007 (UTC)[reply]

Absorption vs. Idempotency

These are treated as the same in the article, but only idempotency is actually discussed. Contrast e.g., http://www.tpub.com/neets/book13/54h.htm Cerberus (talk) 02:34, 7 September 2011 (UTC)[reply]

The section "Connective seniority (symbol rank)" appears to contradict (significantly) pgs 3 and 5 of the book, "Foundations Of Computation" by Critchlow and Eck (2nd ed, 2011)

Regarding the "Connective seniority (symbol rank)" section: https://en.wikipedia.org/wiki/Propositional_formula#Connective_seniority_(symbol_rank)

This section appears to contradict (significantly) the book, "Foundations Of Computation" by Critchlow and Eck (2nd ed, 2011). Pg 3 of that book, which deals with the relative precedences (are precedences the same things as "ranks" / "seniorities" ?), states (but with my additional clarifications in square brackets):

"Parentheses can be used in compound expressions to indicate the order in which the operators are to be evaluated. In the absence of parentheses, the order of evaluation is determined by precedence rules. For the logical operators defined above [i.e., conjunction, disjunction and negation], the rules are that ¬ [i.e., negation] has higher precedence than ∧ [conjunction], and ∧ has precedence over ∨ [disjunction]. This means that in the absence of parentheses, any ¬ operators are evaluated first, followed by any ∧ operators, followed by any ∨ operators."

And then pg 5 adds more operators to the above, stating:

"When these operators [material conditional/implication, biconditional and exclusive or] are used in expressions, in the absence of parentheses to indicate order of evaluation, we use the following precedence rules: The exclusive or operator, ⊕, has the same precedence as ∨ [disjunction]. The [material] conditional operator, →, has lower precedence than ∧, ∨, ¬, and ⊕, and is therefore evaluated after them. Finally, the biconditional operator, ↔, has the lowest precedence and is therefore evaluated last."

In summary, Critchlow and Eck (2nd ed, 2011) give the relative precedences of the logical operators, from highest to lowest, as follows:

   ¬  (negation)
   ∧  (conjunction)
   ∨  (disjunction), ⊕ (exclusive or)      (equal precedence)
   →  (material conditional)
   ↔  (biconditional)

Why does the article give SUCH different rankings?

86.175.18.7 (talk) 14:13, 5 October 2018 (UTC)[reply]

To me, both rankings seem to be almost the same, except that they are presented in orders reverse to each other, (and that and/or are ranked differently). - Jochen Burghardt (talk) 16:42, 6 October 2018 (UTC)[reply]

Jochen, thanks, they do seem more similar as reverses of each other. But they still remain different, and when did "almost the same" become good enough in maths? Use of these different rankings will lead to a given propositional formula evaluating to true for one ranking and false for the other. In arithmetic algebra, we don't have expressions such as (2 * 3 + 4) having one value (6 + 4) in one ranking (or according to one author) and another value (2 * 7) in a different ranking (or according to some other author). So one ranking must surely be "wrong", or at least highly unconventional. (Or is logic just one of those areas in which different practitioners define things differently??) 86.175.18.7 (talk) 13:45, 7 October 2018 (UTC)[reply]

Truth function

A propositional formula is a truth function with arguments propositional variables or propositional constants (simple propositions). Simple propositions/propositional constants have the same status from the point of view of truth values as the propositional variables. The second sentence, re the the truth values of all variables being given/known and determining an unique truth value, indicates this status. The (known) truth values of simple propositions as well as those of the proper propositional variables are replaced in the truth function/propositional formula giving the final truth value, similarly to numerical constants a, b being substituted in an (usual/numeric) algebraic function/formula/expression f(x, y) giving the final numerical value.--178.138.193.100 (talk) 20:53, 13 June 2021 (UTC)[reply]

A propositional formula, like any expression, can be used to define a function. However, this requires to fix the parameters and their order. For example, f(x,y) = (x ∧ ¬y) is different from f(y,x) = (x ∧ ¬y), although the both use the same formula, viz. x ∧ ¬y. - Jochen Burghardt (talk) 09:31, 15 June 2021 (UTC)[reply]

Variable truth value of simple propositions/propositional constants

Simple propositions like "It rains tomorrow/in the next hours." can have a variabile truth value, not known at the present moment. Thus simple propositions can also be propositional variables like p, q. They have the same notation, with small letters.--178.138.195.100 (talk) 21:18, 13 June 2021 (UTC)[reply]

Engineering connectives

The article mentions the so-called "engineering connectives", but without enough details. In what branches of engineering are they called engineering connectives?--178.138.193.100 (talk) 21:26, 13 June 2021 (UTC)[reply]

There is also a sentence with dubious status like "Engineers try to avoid the notions of truth and falsity that... the philosophers.". This sentence should be removed.--178.138.195.100 (talk) 00:41, 14 June 2021 (UTC)[reply]

There is lot of nonsense in the sections mentioning "engineering"; you probably spotted some of them. I guess "engineering connectives" is supposed to mean terminology for logical connectives used in digital electronics. - Jochen Burghardt (talk) 15:36, 15 June 2021 (UTC)[reply]

Notation for propositions and propositional variables or constants in contrast to predicate letters

Propositions from a propositional formula (simple or propositional variables or propositional constants) are denoted with small letters p,q in contrast with predicate letters P, Q, R, S, which asociated to individual constants form propositional constants which can also be present in propositional formulae.--178.138.195.100 (talk) 00:12, 14 June 2021 (UTC)[reply]

The mentioned example of a simple proposition (Five is greater than three.) includes implicitly a predicate letter G (greater than) which also has another (arithmetical) notation ">". Five (5) and three (3) are individual number/numerical constants combined with the implicit predicate letter G.--178.138.195.100 (talk) 00:20, 14 June 2021 (UTC)[reply]

Notation often varies by author.

Propositional logic doesn't consider relation symbols; your analysis of "Five is greater than three" would presuppose predicate logic. - Jochen Burghardt (talk) 15:40, 15 June 2021 (UTC)[reply]

Examples in section "Connective seniority (symbol rank)" contradict each other and the given ordering

Some of them them group AND before OR, others the other way round. And then one example goes from "a & a → b" to "a & (a → b)" despite the ordering giving IMPLICATION a higher rank than AND. Manny123 (talk) 20:32, 7 December 2021 (UTC)[reply]