Mathematical Logic¶

Boolean Algebra¶

Some of the useful constructs are those found in Boolean algebra. In Boolean algebra, we have values true (denoted \(\top\)) and false (denoted \(\perp\)). These comprise the entire domain, but we can create functions on these nevertheless. To describe them, we’ll often use a “truth table” which essentially shows the rules for how the functions behave based on the values of the arguments.

For example, let’s look at conjunction (otherwise known as “and”, and denoted \(\wedge\)):

Thus, \(A\wedge{B}\) is only true when both \(A\) and \(B\) are true, and false otherwise. We also have disjunction (known as “or”, denoted \(\vee\)), implication (denoted \(\rightarrow\), generally stated in English as \(A\rightarrow{B}\) meaning “if A is true, then B is true”), negation (known as “not”, denoted \(\neg\)), and biconditional (known as “equality”, denoted \(\leftrightarrow\) or \(=\) or \(\equiv\)):

We can, of course, combine these functions. They do have an order of operations, with negation evaluated first, then conjunction and disjunction (at the same time), then implication and equality. As in more familiar algebraic rules, we can employ parentheses to group operations so that they are evaluated in the order we desire. For example:

One way to create functions as seen above is to use what is known as disjunctive normal form. We use many terms of conjunctions (possibly negating individual variables) that are then “or”ed together. For example, \(A\vee (B\wedge\neg{C})\vee\neg{B}\). For any function, we can easily create a DNF function that has the same behavior:

1. Create a truth table for the function.
2. For each row that evaluates to true, create a term that is the conjunction of all the variables (if true in that row, add the non-negated version; if false, add the negated version).
3. Create the disjunction of all the terms.

Using the process above, we can, for example create a function for truth table

Thus, \(f(A,B)=(A\wedge{B})\vee(A\wedge\neg{B})\).

We can simplify expressions using a few rules (some of which could be derived from others, but presented for ease of evaluation)

1. \(A\wedge\neg{A}=\perp\)
2. \(A\vee\neg{A}=\top\)
3. \(A\wedge(B\vee{C})=(A\wedge{B})\vee(A\wedge{C})\)
4. \(A\vee(B\wedge{C})=(A\vee{B})\wedge(A\vee{C})\)
5. \(A\vee{B}\vee{C}=(A\vee{B})\vee{C}=A\vee(B\vee{C})\)
6. \(A\wedge{B}\wedge{C}=(A\wedge{B})\wedge{C}=A\wedge(B\wedge{C})\)
7. \(A\vee{B}=B\vee{A}\)
8. \(A\wedge{B}=B\wedge{A}\)
9. \(A\vee\top=\top\)
10. \(A\wedge\top=A\)
11. \(A\vee\perp=A\)
12. \(A\wedge\perp=\perp\)
13. \(A\rightarrow{B}=B\vee\neg{A}\)
14. \((A\leftrightarrow{B})=(A\wedge{B})\vee(\neg{A}\wedge\neg{B})\)
15. \(\neg(A\wedge{B})=\neg{A}\vee\neg{B}\)
16. \(\neg(A\vee{B})=\neg{A}\wedge\neg{B}\)
17. \(\neg(\neg{A})=A\)

Thus, our function is

Adding Predicates¶

Now that we have the rules for evaluating the truth of a logical statement, we might find it more useful to delve to the other side of the problem - how do we create the variables used in a Boolean expression as used above? We can create predicates, that is, functions that take some arbitrary value and return true or false. For example, we could have a function \(Sunny(d)\) which is true if \(d\) is a day and the weather was sunny on that day. We don’t necessarily care how such a function is implimented (maybe it sends a survey and waits for replies, maybe it uses the National Weather Service, maybe it just guesses), but we can start learning more complicated things, by adding predicate-based rules.

For example, if we have our \(Sunny(d)\) predicate, another predicate named \(Hot(d)\) which is true iff (read “if and only if”) \(d\) is a day and it was hot that day, a further predicate \(Hat(d)\) that is true iff people should wear a hat on day \(d\), we can add a rule:

which says that if it is sunny and hot, then people should wear hats. Note: by the way we have defined impliation, this does not mean the converse (if people should wear hats, it is sunny and hot). This may not seem profound, but if we could contact the weather service any time we wanted, but had no idea when to wear a hat, we would now be able to protect ourselves from the sun better. In practice, when we have rules that are true for reasons outside of the ones for Boolean expressions listed above (like for the hat example, we knew we should wear one when it is sunny and hot to protect ourselves from the sun), we can add these rules and start “learning” things by creating new theorems that are useful.

Adding Numbers¶

For us, the most useful application for predicates is working with numbers. We have many relations defined for numbers: \(<\), \(>\), \(\leq\), \(\geq\), and \(=\) which take in two numbers and return true or false; \(+\), \(-\), \(*\), \(/\), \(^\wedge\), \(\%\) and many more that take in numbers and produce other numbers. So, we might have a predicate \(P(x,y)=(x\leq{y})\vee(x*y<0)\).

Quantifiers, Domains, and Bound Variables¶

Before we can talk about properties of relations (helpful for proving things), we must introduce the concept of quantifiers. There are exactly two of them, and they are fairly straightforward.

\(\forall\) is the “universal quantifier” that means “for all”. So, we might have a statement \(\forall{x}:(x<0)\vee(x\geq0)\). That means, for all \(x\) in the domain we are working with (the real numbers, natural numbers, rational numbers, etc.), \(x\) is either less than zero or greater or equal to zero (which tells us nothing about the value of \(x\), but is a true statement).

\(\exists\) is the “existential quantifier” that means “there exists”. Here, we might have a statement \(\exists{x}:x^2=25\). That means that there exists an \(x\) in the domain that, when squared, equals 25. Note that both \(x=5\) and \(x=-5\) satisfy this (depending on whether we allow negative numbers). The existence quantifier just cares that there is at least one case in which the expression is true.

Instead of assuming a domain based on the problem at hand, we can specify it exactly using \(\in\). \(\in\) is true iff the argument on the left-hand side is a an element of the set given as the argument on the right-hand side. Some sets that are useful are:

• \(\mathbb{N}\), the natural numbers. These are the numbers starting at 0 or 1 (depending on whether you’re a physicists, mathematician, or computer scientist), that are generated by the successor relation \({\textrm{succ}}(n)=n+1\). So, \(\mathbb{N}=\{0,1,2,...\}\). Note, that the natural numbers do not include an “infinity” (\(\infty\)): \(\infty\) must satisfy \(\forall{x\in\mathbb{N}}:x\leq\infty\), stating that \(\infty\) must be the largest of the natural numbers. But, with our successor relation, we just add 1, and make a bigger one. Thus, each natural number must be finite.
• \(\mathbb{Z}\), the integers. These are the numbers created by extending the natural numbers to the negatives (many ways to generate them). So, \(\mathbb{Z}=\{..., -2, -1, 0, 1, 2, ...\}\), similarly not including positive or negative infinity.
• \(\mathbb{Q}\), the rational numbers. These are the numbers of the form \(\frac{p}{q}\) where \(p\in\mathbb{Z}\) and \(q\in(\mathbb{Z}\backslash\{0\})\) (meaning \(q\) is any integer except 0).
• \(\mathbb{R}\), the real numbers. These are any number along the continuous number line. So along with any rational number, we include numbers that cannot be expressed as fractions such as \(\pi\), \(\sqrt{2}\), or \(e\). For physics, this is usually the domain we are interested in, as physical quantities are generally taken to be continuous (not always the case, of course).

We can also employ the idea of a range of values such as \([0,1)\) which is the set of all numbers between 0 and 1 along the number line (real numbers), including 0 but excluding 1. So, we might have a statement such as

which just says that if we take any natural number \(x\) and any real number \(y\) and add them, we get another real number \(z\).

In these formulae, we have the consideration of scope, much as we have seen in Mathematica with local variables in a Module (see Modules). When we introduce a variable using a quantifier, that defines where it is “bound” in that if we say \(\forall{x\in[0,1)}:P(x,y)\), \(x\) is bound to the statement, and is given to be in the range \([0,1]\). \(y\), however, is “free”, in that we have placed no restriction on it in this statement, meaning that the statement is dependent upon the value given to \(y\).

Properties of Relations¶

We can talk about properties for the binary relations above (such as \(<\)) using the language we’ve built up. Let \(R\) be a binary relation that produces a truth value and let \(xRy\) represent applying the function to arguments \(x\) and \(y\) (think if \(R\) is \(<\), then we’d say \(x<y\)).

• Reflexivity: \(\forall{x}:xRx\). For example, \(=\) since \(x=x\) is trivially true for any \(x\). But, \(xRy\equiv (x^2>y)\) is not reflexive over the real numbers, since for \(0<x<1,~x^2<x\).
• Symmetry: \(\forall{x}\forall{y}:(xRy\rightarrow{yRx})\). For example, \(xRy\equiv (x<5)\wedge (y<5)\) is symmetric (if we swap the arguments when both are less than 5, we still get \(\top\)), but \(xRy\equiv x<y\) is not symmetric, since \(2<5\) is true, but \(5<2\) is false.
• Asymmetry: \(\forall{x}\forall{y}:(xRy\rightarrow\neg{yRx})\). For example, \(xRy\equiv{x<y}\) is asymmetric (when we have \(x<y\), we know if we swap the arguments, we get the opposite result - and we have no trouble with \(xRx\) since it is always false). But, \(xRy\equiv{x=y}\) is not asymmetric since if we swap arguments, we get the same result as before.
• Antisymmetry: \(\forall{x}\forall{y}:(xRy\wedge yRx)\rightarrow x=y\). For example, \(xRy\equiv{x\leq{y}}\) is antisymmetric since if both \(x\leq{y}\) and \(y\leq{x}\), \(x\) and \(y\) must be the same. But, \(xRy\equiv (x<5)\wedge (y<5)\) is not antisymmetric since we have \({\small{2}}R\small{4}\) and \({\small{4}}R\small{2}\), but \(2\ne4\).
• Transitivity: \(\forall{x}\forall{y}\forall{z}:(xRy\wedge yRz)\rightarrow xRz\). For example, \(xRy\equiv(x<y)\) is transitive since if \(x<y\) and \(y<z\) it must be true that \(x<z\). But, \(xRy\equiv(\gcd(x,y)=1)\) is not ( \(\gcd(2,3)=1,~\gcd(3,10)=1\) but \(\gcd(2,10)=2\)).
• Totality: \(\forall{x}\forall{y}:(xRy\vee{yRx})\). For example, \(xRy\equiv(x\leq{y})\) is total since we are essentially saying that \(x<y\) or \(y<x\) or \(y=x\) which is certainly the case for the real numbers. But, \(xRy\equiv(x<y)\) is not (\(5<5\) is false).

There are other such properties of binary relations as well. Equivalence relations are those that are reflexive, symmetric, and transitive (like \(=\)). Partial order relations are those that are reflexive, antisymmetric, and transitive (like \(=\) and \(\leq\)). Total order relations are those that are partial orders and total.

While each of these properties are obvious for familiar examples, they are worth considering when trying to create relations to apply assumptions or bound problems. If we don’t do so carefully, sometimes Mathematica may not be able to solve problems in a useful way. A small example is

Solve[Cos[x] == 0, x]

which gives

{{x -> ConditionalExpression[-(\[Pi]/2) + 2 \[Pi] C[1], C[1] \[Element] Integers]},
{x -> ConditionalExpression[\[Pi]/2 + 2 \[Pi] C[1], C[1] \[Element] Integers]}}

But, if we restrict the problem:

Solve[{Cos[x] == 0, x > 0, x < 2 Pi}, x]

which gives {{x -> \[Pi]/2}, {x -> (3 \[Pi])/2}}. In this case, Mathematica could solve the original problem, but did so very generally, overcomplicating the expression if we just want a couple solutions for \(x\in(0,2\pi)\).