Concerning the logical projection: How to express nullary and unary operations as binary operations?

Question

Let P and Q be two statements, each having two possible truth values: true (T) or false (F). Then there are exactly 16 unique compound statements involving P and Q with corresponding truth tables of the form (w,x,y,z). We have given symbols to some of these truth tables; for example, when P has truth table (T,T,F,F) and Q has truth table (T,F,T,F), then

• We write the statement corresponding to (T,F,T,T) as P⇒Q
• We write the statement corresponding to (T,F,F,T) as P⊽Q
• We write the statement corresponding to (T,F,F,T) as P⇔Q

Note that these compound statements are logically equivalent to other expressions:

• The statement P⇒Q has the same truth table as ¬P∨Q
• The statement P⊽Q has the same truth table as ¬(P∨Q)
• The statement P⇔Q has the same truth table as (P⇒Q)∧(P⇐Q)

Note in each of the examples above, the compound statement is written at first in the form P(?)Q, and then in a more complicated expression. That is, the first expression writes the compound statement as a binary operation of P and Q. For instance:

• The implication maps (P,Q) to P⇒Q
• The logical nor maps (P,Q) to P⊽Q
• The biconditional maps (P,Q) to P⇔Q

Now the binary operation which maps (P,Q) to P is called the logical projection onto P, and the binary operation which maps (P,Q) to Q is called the logical projection onto Q. My question is: What symbol can be used to represent these two logical projections as binary operations? That is, how can we write these two logical projections in the form P(?)Q and P(¿)Q? Do these two projection operations have recognized symbols? Unfortunately the Wikipedia page for logical projection looks like it has a lot of room for expansion.

(Note: P and Q are essentially "unary operations"; for the purpose of my question we could have considered the other unary operations ¬P or ¬Q or even the two nullary operations ⊤ and ⊥.)

Edit:

After some time, I seem to have found a possible answer: Donald Knuth, in his section on Boolean Basics in The Art of Computer Programming Volume 4A, Pre-Fascicle 0B, writes the logical projections as P L Q and P R Q. That is, we could express projection onto P as the binary operationL(P,Q) and express projection onto Q as the binary operation R(P,Q). See this StackExchange question for how to typeset these symbols.

Answer 1

You can find this discussed in introductory texts for digital electronics or low level programming. I remember reading my 3 year older sister's high school textbooks where logic was discussed. Then already when I entered high school, this was in Norway in 1978, most of the material on logic had been removed, although the notation, with e.g. ∧, ∨ and ¬ denoting respectively AND (conjunction), OR (disjunction) and NOT (negation), was still discussed.

The truth table (a, b, c, d) denotes the function

a∧(P∧Q) ∨ b∧(P∧¬Q) ∨ c∧(¬P∧Q) ∨ d∧(¬P∧¬Q)

This is called disjunctive normal form, because it's a disjunction of individual conjunctions of the possible combinations of terms.

You do not have to define each such table separately.

---

And so, for example, the truth table (T, F, T, F) denotes the function

T∧(P∧Q) ∨ F∧(P∧¬Q) ∨ T∧(¬P∧Q) ∨ F∧(¬P∧¬Q) ≡
T∧(P∧Q) ∨ T∧(¬P∧Q) ≡ P∧Q ∨ ¬P∧Q ≡
(P ∨ ¬P)∧Q ≡
T∧Q ≡
Q

If you want an expression that involves P you can just choose any one before the first simplification where P disappears, or you can construct such as one.

E.g. Q ≡ Q ∨ F ≡ Q ∨ P∧¬P.

IF you want a symbol for it you'll have to define one, because there's no commonly used symbol. E.g. you can define PβQ ≡ Q, or whatever.

---

Not quite arbitrary association 1:

PβQ≡Q can be viewed as a special case of an indexing operation choose(F,P,Q)≡Q and choose(T,P,Q)≡P. I.e., the first argument decides which of the two following arguments should be the result. All binary logical functions can be expressed in terms of such indexing, e.g. P∧Q≡choose(P,Q,F). And this connection is used in many scripting languages to represent the result of a logical expression as one of the argument objects. E.g., in Javascript, IIRC,

my_namespace = my_namespace || {}

where my_namespace is an identifier to be defined if it isn't already, = denotes assignment (which creates an identifier if it doesn't exist), my_namespace on the right hand side evaluates to logical False if it doesn't yet exist, || denotes logical OR, and {} denotes a new object, which is the result of the OR-expression if my_namespace evaluates to False.

It's also the basis of boolean short-circuit evaluation in a great many programming languages.

---

Not quite arbitrary association 2:

In pixel based graphics there is an operation that takes an area of one image, and an area of another, and applies an arbitrary bit-level combination specified as a truth table. It was a result of the Smalltalk project at Xerox Parc, where it was identified as one of the crucial elements required to implement a graphical user interface. At that time it was called “bitblt”, short for “bit block transfer”, and e.g. the Windows API has a BitBlt function, plus a number of variations & extensions.

Answer 2

It is not possible to express P, ¬P, Q, ¬Q, T or ⊥ in a statement of the form (¬)P R (¬)Q, where R ∈ {→, ∧, ∨, ⊕, ↔}: you can simply try all possibilities.

Normally we would not require a compound statement and would be happy with a 'plain' statement, in which case all the above are already in normal form.

If you really want to express P in a statement with both P and Q, you could try something like

P ≡ P ∧ (Q ∨ ¬Q)
P ≡ P ∨ (Q ∧ ¬Q) ≡ P ∨ Q ∧ ¬Q        (brackets are redundant since ∧ binds stronger than ∨)

And similarly for the others. Note that the last equivalence actually gives you something of the form P(?)Q, with ?=∨Q∧¬.

Answer 3

By far the most common notation for the "project to the first component" binary operation applied to P and Q is simply P.

As a practical matter, you pretty much never need a symbol to represent projection as a binary operation on values: the need mainly only arises when you have occasion to write it as a unary operation on pairs of values.

e.g. if we defined swap(P,Q) = (Q,P), we might want to write an equation

ρ₂ o swap = ρ₁

where I've used ρ₁ for "project to the first component" and o for composition. Usually when a symbol is given, it's some variation on the letter p; e.g. p, ρ, π. e.g. ρ₁(P,Q) = P.

Answer 4

There is a rigid standard from Abstract Algebra, that might give this structure. The group known as Bourbaki proposes that the clearest way of communicating operations is postfix, and they propose some very rigid translations back into more normal forms from postfix. By applying their standards, we can get some ideas.

The propose a preferred form and two alternatives for readability:

1. postfix PQ+, P Q+ or P,Q+
2. prefix +(P,Q) with the parentheses signifying the reversed order
3. infix P + Q the notation everyone else in the world prefers

For projection, I would suggest we simply apply these equivalences in reverse.

Since there is a tradition of writing X_n, and therefore (P,Q, ... S)_n to select item 2 from the list. And since logicians always start counting at zero. We can let (P,Q)₀ be the selector for P and (P,Q)₁ be that for Q. Infix-ified these would be P ₀ Q and P ₁ Q. To be happily clear, up to Bourbaki standards, the spacing is mandatory. After all P could have subelements.

The nullary operations are also straightforward, the Top and Bottom elements can just as easily be considered of any arity you wish, and always result in their constant values. So we can have P ⊤ Q for the constant true and P ⊥ Q for the constant false.

The two 'nots' get a little silly. But taking P ¬ Q to simply be ¬ Q, ignoring the P, suggests we look for a graphical inversion of the original not like P ⨽ Q to represent the not of P, ignoring Q.