1

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.

  • One a tiny bit more traditional is the subscript 0 and the subscript 1 (which are hard to type in a comment). It avoids language dependence, and keeps with the standard "Anti-Bourbaki" notation of making what would otherwise be binary relations consistently infix. P<sub>0</sub>Q would be (P, Q)<sub>0</sub>, index zero of the sequence (P,Q), and similarly for 1. – jobermark Sep 8 '15 at 1:19
  • @jobermark I really like that suggestion as well. Where have you seen this used before? The only other question - if you let P ≡ P_0 Q and Q ≡ P_1 Q, how would you denote ¬P and ¬Q? – Mathemanic Sep 8 '15 at 1:23
  • As to source: There is a school of Algebra known as Bourbaki, they want a totally consistent notation, and they strongly prefer postfix notation. So they use P,Qx but allow for x(P,Q), and for completeness sake the original algebraic notations of P x Q. As to forcing the final case. Perhaps P ¬ Q could simply mean ¬Q and if you can get the mirror image of ¬, I would use it P⨽Q to be ¬P. Then top and bottom could just be infixed but ignore their operators. P⊥Q = false and P⊤Q = true. But it all seems a bit precious. – jobermark Sep 8 '15 at 1:32
  • Thanks for your reply @jobermark. Can you elaborate that into an answer? – Mathemanic Sep 8 '15 at 23:09
3

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.

  • Hi @cheers-and-hth-alf , thanks for the fantastic answer! I was just wondering, could you please say a little bit more about the logical indexing operation? For example, why does choose(P,Q,F)≡P∧Q? Also, why does the function sometimes take T as an argument and other times take F as an argument? (If both T and F are in the domain of the function, shouldn't they always both be arguments?) – Mathemanic Oct 22 '16 at 17:17
  • @Mathemanic; Regarding “why does choose(P,Q,F)≡P∧Q”. First the notation is from the question: F stands for False, and T stands for True. P and Q are propositions that can be True or False. Many programming languages have a choice operation, e.g. in Python it's expressed as P if condition else Q, in C, C++, Java, C#, JavaScript etc. it's condition? P : Q, and in Excel (a spreadsheet program) it's if( condition, P, Q ). Now, P∧Q=T if and only if both of P and Q are T. So if P=T, then P∧Q=T iff Q=T. That gives choice(P,Q,?), where the ? is for the case P=F. And in that case P∧Q=F, so ?=F. – Cheers and hth. - Alf Oct 22 '16 at 22:20
  • In passing, if one defines F<T (an ordering of the values), then P∧Q=min(P,Q), and P∨Q=max(P,Q), which is a nice alternative definition that extends in a practical way to three-value logic. – Cheers and hth. - Alf Oct 22 '16 at 22:23
  • Regarding “why does the function sometimes take T as an argument and other times take F as an argument”, the first argument is intended to be a boolean, i.e. one of the values F and T. The second and third arguments could be anything, but in the example of using choice to define logical AND, the second and third arguments are also booleans. – Cheers and hth. - Alf Oct 22 '16 at 22:27
1

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∧¬.

1

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.

  • Hi Hurkyl! This is definitely one of my favorite suggestions (although I might prefer ρ₀ and ρ₁, instead of ρ₁ and ρ₂). I think this might be the most feasible solution yet. Thanks for the great ideas! – Mathemanic Sep 9 '15 at 23:44
1

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 Xn, 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)0 be the selector for P and (P,Q)1 be that for Q. Infix-ified these would be P 0 Q and P 1 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.