Compound Statements Discussion

(The following is/are the initial prompt(s) for an online discussion; students may have posted responses, and prompts for further discussion may have been added, but these things are not shown.)

So far we have somewhat casually seen words such as “and,” “or,” “if,” etc. used in mathematical statements. These so-called “connectives” have specific meanings in logic, and this discussion helps you get familiar with those meanings. Use the following questions as starting points for exploring connectives, and post your thoughts, questions, answers, comments, etc.

Exclusive Or

The textbook mentions an “exclusive or” connective, P exclusive-or Q, which is true if and only if exactly one of P or Q is true. Define this connective more precisely by giving a truth table for it.

Logic and Arithmetic

You might have heard that computers represent numbers in “binary,” or base-2 (then again, of course, you might not have heard this — but they really do). The reason is that there is a close connection between the rules for binary arithmetic and logic.

Recall that in base-2, the only possible digit values are 0 and 1.

The rules for adding 1-digit base-2 numbers x and y are as follows (ignoring any carry for now): if x and y are both 0, then the sum is 0; if exactly one of x and y is 1 and the other is 0, the sum is 1; if both of x and y are 1, the sum is 0. Suppose P is the statement “x is 1” and Q is the statement “y is 1.” Notice that because there are only 2 digit values, ¬P is the same as “x is 0,” and ¬Q is the same as “y is 0.” Can you write the rule for adding two 1-digit base-2 numbers as a logical expression using the connective symbols ∧, ∨, and/or ¬?

The rule for having a carry when you add 1-digit base-2 numbers x and y is that if x and y are both 1 then there is a carry, otherwise there isn’t. Defining P and Q as above, can you write this rule as a statement using ∧, ∨, and/or ¬?

Can you formulate rules for subtracting 1-digit base-2 numbers, specifically rules that say when the difference is 0 and when it is 1, and when you need to borrow from a higher-order digit position? Can you write these rules as compound logical statements?

Truth Tables

Truth tables are very helpful tools for understanding when a compound statement is true and when it is false. For example, see if you can give truth tables for the following (notice that Canvas’s “Table” menu might be helpful for posting tables that you create).

\[\lnot ( P \land Q )\]  

\[\lnot P \lor \lnot Q\] 

\[( P \land \lnot Q) \rightarrow \lnot R\] 

Can you use a truth table to show that \[(\lnot P \lor Q) \leftrightarrow (P \rightarrow Q)\] is a tautology?