31:T6e6,## The Boolean operators First, let's take a close look at four binary, Boolean operations: - Conjunction, denoted by ∧ and corresponding *roughly* to the word "and", - Disjunction, denoted by ∨ and corresponding *roughly* to the word "or", - Implication, denoted by ⇒ and corresponding *roughly* to the word "implies", and - Biconditional, denoted by ⇔ and corresponding *roughly* to the phrase "if and only if". These are connectives in the most basic formulation of mathematical logic, known formally as [*propositional calculus*](https://en.wikipedia.org/wiki/Propositional_calculus). The idea is to formulate logic in an algebraic way. When we write something like > If ${tex`n`} is even, then ${tex`n^2`} is even, we can identify that as a specific case of ${tex`p⇒q`}, where - ${tex`p`} represents the statement that ${tex`n`} is even and - ${tex`q`} represents the statement that ${tex`n^2`} is even. If we then study the properties of this algebraic system, we can draw conclusions about mathematical logic quite generally. Now, just as we use multiplication tables when studying the operation of multiplication of integers, we can use tables to help us understand the Boolean operations. It's actually much simpler because, given a statement like ${tex`p`}, there are only two possible values of ${tex`p`}, namely true (T) or false (F). Given a binary operation and two inputs ${tex`p`} and ${tex`q`}, there are only four possible input pairs TT, TF, FT, and FF. Thus, we can actually *define* each Boolean operation by specifying exactly what value (T or F) that operation should assign for each of those pairs. We then display those in a so-called *truth table*. Here is the truth table that defines those four basic operations:32:T429,

p	q	p∧q	p∨q	p⇒q	p⇔q
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

33:Tda8,In my experience teaching introductory undergraduate courses involving propositional calculus, there's rarely any confusion over the ∧, ∨, and ⇔ columns. They all seem to correspond closely with the intuitive understanding the students bring to class. The ⇒ column, though, is another matter and always seems to generate a lot of questions. Typically, that discussion centers on student attempts to reconcile the truth column with their understanding of the word "implies". **I tend to think that is a mistake to focus on the English meanings of the terms we use to describe these operations, since the connotations of those terms vary by context. The operations, by contrast, should be precisely defined Boolean operators that are useful for propositional logic.** It's easy to see examples of this for "or" (∨). If I need to decide if I'm going to McDonald's or [Atomix](https://www.theworlds50best.com/the-list/31-40/atomix.html) for dinner, I'm probably not going to both. Thus, perhaps T∨T should be F. If you're a big eater, you might argue - but, that's exactly the point. The English language is no place to start an axiomatic system for deductive logic. The situation is even more subtle for ⇒, which is exactly why that column leads to confusion. If you're not careful, you'll find yourself arguing whether it absolutely has to be cloudy when it's raining. ## What do we want from these operators? An alternative point of view is to focus on the utility these definitions yield. At a minimum, these definitions should imply the basic rules of inference: - [Modus Ponens](https://en.wikipedia.org/wiki/Modus_ponens): ${tex`p∧(p⇒q)⇒q`} and - [Modus Tollens](https://en.wikipedia.org/wiki/Modus_tollens): ${tex`¬q∧(p⇒q)⇒¬p`}. Note that these statements are pillars of mathematical logic. Any time you apply a theorem by verifying that it's hypotheses are satisfied and apply the implication to draw a conclusion, you are applying Modus Ponens. When you write an indirect proof by proving the contrapositive, you are applying Modus Tollens. Verification that our definitions of ∧ and ⇒ yield Modus Ponens and Modus Tollens is a simple matter of examining their truth tables:

Truth table for Modus Ponens

${trueTruthTable("p&(p=>q) => q")}

Truth table for Modus Tollens

${trueTruthTable("!q & (p=>q) => !p")} The fact that we've got a column of all True in the far right of these truth tables indicates that the formulae are tautologies; true in all circumstances. **This is exactly why we are OK with T,F,T,T as a definition for p⇒q - because, this definition validates the two fundamental rules of inference.** ## Alternatives? The fact that the definition of ${tex`⇒`} (together with the definition of ${tex`∧`}) yields the rules of inference is not quite sufficient to accept that definition alone. Perhaps there is some sequence other than T,F,T,T that would work as well? To help us explore this possibility, I've constructed a variable implies operator, denoted →. By a *variable* operator, I mean that we can change it's defining truth values from T,F,T,T to any other sequence of four Ts and Fs. Since there are 4 slots and 2 potential values for each slot, there are a total of ${tex`2^4=16`} possible definitions for →. The slider below allows you to examine the truth table for just p→q for all 16 of these:34:T522,## Credits and changes The code used to generate these tables is based almost entirely on [Vinicius Mello's Truth Table notebook](https://observablehq.com/@vinicius-mello/truth-table). I've made a few small changes to adapt to my purposes here. First, the original notebook uses the following notation: - Implication: Unicode → and ASCII `->` - Biconditional: Unicode ↔ and ASCII `<->` I've changed those to - Implication: Unicode ⇒ and ASCII `=>` - Biconditional: Unicode ⇔ and ASCII `<=>` to match the notation I typically use in class. More importantly, I've redefined → to the new *variable* operator. To accomplish that, I encapsulated most of the code in the original notebook into a single `truthTableFunction` function, with a few changes. `truthTableFunction` accepts a single argument `bits` which should be an array of length 4, each of whose values is either `true` or `false`. `truthTableFunction` then returns a function that accepts a string representing a statement of propositional logic and returns the corresponding truth table. Of course, you can use any truthy or falsey values; I usually uses 1s and 0s. For example, you might generate the following faux truth table to illustrate why the identically true definition for ${tex`p→q`} might not be such an outstanding idea:35:T5ba,function truth_slider(value, label) { let seqs = [[0], [1]]; for (let i = 0; i < 3; i++) { seqs = seqs.map((a) => [a.concat([0]), a.concat([1])]).flat(); } let bits = d3.create("div"); let bitElem = bits.node(); bitElem.value = value; let cur_value = seqs.map((c) => test(c, value)).indexOf(true); bits.append("div").style("font-weight", "bold").html(label); let step = bits.append("button").text("^"); let slider = bits .append("input") .attr("type", "range") .attr("min", 0) .attr("max", 15) .attr("step", 1) .attr("value", cur_value) .style("margin-left", "10px"); let bit_display = bits .append("div") .style("display", "inline-block") .style("margin-left", "10px") .html(`[${value.map((t) => (t ? "T" : "F"))}]`); slider.on("input", function () { cur_value = parseInt(this.value); bitElem.value = seqs[cur_value]; bit_display.html(`[${seqs[cur_value].map((d) => (d == 1 ? "T" : "F"))}]`); bitElem.dispatchEvent(new CustomEvent("input")); }); step.on("click", function () { cur_value = (parseInt(slider.node().value) + 1) % 16; slider.node().value = cur_value; bitElem.value = seqs[cur_value]; bit_display.html(`[${seqs[cur_value].map((d) => (d == 1 ? "T" : "F"))}]`); bitElem.dispatchEvent(new CustomEvent("input")); }); return bitElem; function test(a, b) { return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]; } }36:T1e28,function truthTableFunction(bits = [1, 0, 1, 1]) { function truthTable(exp) { const data = []; const sub = []; const f = logicParser(exp); const text = textFormula(f); const subText = {}; const subPush = (f) => { if (subText.hasOwnProperty(f.text)) return; sub.push(f); subText[f.text] = true; }; function trav(f) { if (f.node === "Literal") { subPush(f); return; } if (f.node === "Not") { trav(f.child[0]); subPush(f); return; } trav(f.child[0]); trav(f.child[1]); subPush(f); } trav(f); const alignment = {}; sub.forEach((f) => (alignment[f.text] = "center")); let vars = variables(f); for (let v of values(vars)) { const row = {}; for (let i = 0; i < sub.length; ++i) { row[sub[i].text] = evalFormula(sub[i], v) ? "T" : "F"; } data.push(row); } return Inputs.table(data, { layout: "auto", align: alignment }); } function textFormula(f) { const precedence = { Or: 2, And: 2, Implies: 3, WeakImply: 3, Not: 1, Literal: 0 }; const paren = (f, op) => precedence[f.node] >= precedence[op] ? "(" + textFormula(f) + ")" : textFormula(f); if (f.text === undefined) { switch (f.node) { case "Literal": f.text = f.value; break; case "Or": f.text = paren(f.child[0], "Or") + "∨" + paren(f.child[1], "Or"); break; case "Xor": f.text = paren(f.child[0], "Xor") + " ⊕" + paren(f.child[1], "Xor"); break; case "And": f.text = paren(f.child[0], "And") + "∧" + paren(f.child[1], "And"); break; case "Implies": f.text = paren(f.child[0], "Implies") + "⇒" + paren(f.child[1], "Implies"); break; case "Equiv": f.text = paren(f.child[0], "Equiv") + "⇔" + paren(f.child[1], "Equiv"); break; case "Not": f.text = "¬" + paren(f.child[0], "Not"); break; case "WeakImply": f.text = paren(f.child[0], "WeakImply") + "→" + paren(f.child[1], "WeakImply"); break; } } return f.text; } function* values(vars) { const n = vars.length; for (let i = 0; i < 2 ** n; ++i) { let vl = {}; let b = 1; for (let j = n - 1; j >= 0; --j, b *= 2) { vl[vars[j]] = (b & i) == 0; } yield vl; } } function variables(f) { const v = {}; function vr(f) { if (f.node === "Literal") { v[f.value] = true; return; } f.child.forEach((c) => vr(c)); } vr(f, v); return Object.keys(v).sort(); } function evalFormula(f, v) { if (typeof f === "string") f = logicParser(f); function ef(f) { if (f.node === "Literal") return v[f.value]; if (f.node === "And") return ef(f.child[0]) && ef(f.child[1]); if (f.node === "Or") return ef(f.child[0]) || ef(f.child[1]); if (f.node === "Implies") return !ef(f.child[0]) || ef(f.child[1]); if (f.node === "Equiv") return ef(f.child[0]) === ef(f.child[1]); if (f.node === "Xor") { const a = ef(f.child[0]); const b = ef(f.child[1]); return (a || b) && !(a && b); } if (f.node === "Not") return !ef(f.child[0]); if (f.node === "WeakImply") { return explicit_formula(...bits)(ef(f.child[0]), ef(f.child[1])); } } return ef(f); } const expParserData = { tokens: { Space: /\s+/, Literal: /\w+/, Or: [/∨/, /\|/], And: [/∧/, /&/], Implies: [/⇒/, /=>/], WeakImply: [/→/, /->/], Equiv: [/⇔/, /<=>/], Xor: [/⊕/, /\^/], Not: [/¬/, /\!/], LeftParen: /$/, RightParen: /$/ }, binaryOp: ["Or", "And", "Implies", "WeakImply", "Equiv", "Xor"], precedence: { Or: 3, And: 3, Xor: 3, Implies: 2, WeakImply: 2, Not: 4, Equiv: 1 }, associativity: { Implies: "Right", Equiv: "Right", WeakImply: "Right" }, unaryOp: ["Not"], terminal: ["Literal"] }; let logicParser = expressionParser(expParserData); function tokenizer(lex) { const lexa = Object.entries(lex); lex = []; lexa.forEach(([a, b]) => { if (b instanceof RegExp) lex.push([new RegExp("^(" + b.source + ")(.*)"), a]); else b.forEach((t) => lex.push([new RegExp("^(" + t.source + ")(.*)"), a])); }); return (str) => { let s = str; const r = []; while (s) { let flag = true; for (let i = 0; i < lex.length; ++i) { let m = s.match(lex[i][0]); if (m) { const l = lex[i][1]; r.push([l, m[1]]); s = m[2]; flag = false; break; } } if (flag) throw "SyntaxError: invalid token"; } r.push(["End", ""]); return r; }; } function expressionParser(data) { const to = tokenizer(data.tokens); const binaryOp = {}; data.binaryOp.forEach((op) => (binaryOp[op] = true)); const isBinary = (tok) => binaryOp.hasOwnProperty(tok); const unaryOp = {}; data.unaryOp.forEach((op) => (unaryOp[op] = true)); const isUnary = (tok) => unaryOp.hasOwnProperty(tok); const terminal = {}; data.terminal.forEach((op) => (terminal[op] = true)); const isTerminal = (tok) => terminal.hasOwnProperty(tok); const prec = (tok) => data.precedence[tok]; const associativity = (tok) => !data.associativity.hasOwnProperty(tok) ? "Left" : data.associativity[tok]; return function (str) { const l = to(str).filter(([tok, _]) => tok !== "Space"); let it = 0; const next = () => l[it][0]; const value = () => l[it][1]; const consume = () => (it = it + 1); const expect = (tok) => { if (next() === tok) consume(); else throw "SyntaxError: unexpected token"; }; let Eparser, Exp, P; const binary = (tok) => { return tok; }; const unary = (tok) => { if (isBinary(tok)) return "Unary" + tok; else return tok; }; Eparser = () => { const t = Exp(0); expect("End"); return t; }; Exp = (p) => { let t = P(); while (isBinary(next()) && prec(binary(next())) >= p) { const op = binary(next()); consume(); const q = prec(op) + (associativity(op) === "Right" ? 0 : 1); const t1 = Exp(q); t = { node: op, child: [t, t1] }; } return t; }; P = () => { if (isUnary(next())) { const op = unary(next()); consume(); const q = prec(op); const t = Exp(q); return { node: op, child: [t] }; } else if (next() === "LeftParen") { consume(); const t = Exp(0); expect("RightParen"); return t; } else if (isTerminal(next())) { const t = { node: next(), value: value() }; consume(); return t; } else throw "SyntaxError: "; }; return Eparser(); }; } function explicit_formula(z1, z2, z3, z4) { let f = (p, q) => { if (p && q) { return Boolean(z1); } else if (p & !q) { return Boolean(z2); } else if (!p & q) { return Boolean(z3); } else if (!p & !q) { return Boolean(z4); } }; return f; } return truthTable; }37:[] 2f:{"title":"The definition of ⇒","cells":[{"id":0,"value":"# The definition of ⇒\n\nThe definition of the Boolean operator ⇒ often leads to confusion among students studying elementary logic. So, let's take a close look at how Boolean operators are defined in the first place and why we make the specific choices we do. Part of the task will involve examining all the possible alternatives to ⇒ - a task that's been automated for this presentation.","pinned":false,"hidden":false,"mode":"md"},{"id":418,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":401,"value":"$32","pinned":false,"hidden":false,"mode":"html"},{"id":421,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":614,"value":"viewof bits0 = truth_slider([1, 0, 1, 1], \"The → column\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"implies_column = {\n let truthTable = truthTableFunction(bits0);\n return truthTable(\"p->q\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":641,"value":"We're mostly interested in applying this variability to see which of the possible definitions of → make both Modus Ponens and Modus Tollens tautologies. To do so, let's build the truth tables for their conjunction:\n${tex.block`(p∧(p→q)→q)∧(¬q∧(p→q)→¬p).`}\nUsing the slider, we can quickly examine all 16 possibilities. You can also use the ${html`