Lecture 1

Topics: propositions, basic connectives (NOT, AND, OR, XOR, IMPLIES, IFF), deMorgan's Laws, implication in everyday language, contrapositive, converse, logical equivalence.

In the following questions, assume that \(x\) and \(y\) are fixed integers, and consider the following statement \(S\): \[ (x = 0) \textrm{ IMPLIES } (xy = 0) \]

If we know that \(x=0\), then what do we know about the value of \(xy\)?

(a) We don't know anything about \(xy\)

INCORRECT! The hypothesis of \(S\) is true, and the conclusion gives us information about the value of \(xy\).

(b) \(xy = 0\)

CORRECT! We know that the hypothesis \(x=0\) is true, so the conclusion \(xy=0\) must be true.

(c) \(|xy| > 0\)

INCORRECT! This is equivalent to saying that \(xy\) is non-zero.

(d) \(xy=y\)

INCORRECT! It's true when \(y=0\), but we don't know if that is the case.
If we know that \(x \neq 0\), then what do we know about the value of \(xy\)?

(a) We don't know anything about \(xy\)

CORRECT! The implication only allows us to conclude something when the hypothesis is true, that is, when \(x=0\).

(b) \(xy = 0\)

INCORRECT! It's true when \(y=0\), but we don't know if that is the case.

(c) \(|xy| > 0\)

INCORRECT! It's true when \(y \neq 0\), but we don't know if that is the case.

(d) \(xy=y\)

INCORRECT! It's true when \(y=0\) or \(x=1\), but we don't know if either of those are true.
If we know that \(xy = 0\), then what do we know about the value of \(x\)?

(a) We don't know anything about \(x\)

CORRECT! If the conclusion of an implication is true, the hypothesis can be either true or false.

(b) \(x = 0\)

INCORRECT! It's possible that \(y=0\) and \(x \neq 0\).

(c) \(|x| > 0\)

INCORRECT! It's not true when \(y \neq 0\).

(d) \(x=y\)

INCORRECT! It's possible that one of \(x\) or \(y\) is non-zero.
If we know that \(xy \neq 0\), then what do we know about the value of \(x\)?

(a) We don't know anything about \(x\)

INCORRECT! The contrapositive of the statement \(S\) gives us information when \(xy \neq 0\).

(b) \(x = 0\)

INCORRECT! If this was true, then the hypothesis of \(S\) would be correct, so it would follow that \(xy = 0\).

(c) \(|x| > 0\)

CORRECT! The contrapositive of the statement \(S\) is \[ (xy \neq 0)\ \textrm{ IMPLIES }\ (x \neq 0) \] and we know that the hypothesis \(xy \neq 0\) is true, so the conclusion \(x \neq 0\) is true. This is equivalent to saying \(|x| > 0\).

(d) \(x=y\)

INCORRECT! It's possible that \(x=3\) and \(y=4\).

Suppose that you are taking a class, and that class has a textbook and a final exam. Let the propositional variables \(\) have the following meanings: \[ P = \textrm{You get an A on the final exam} \] \[ Q = \textrm{You do every exercise in the book} \] \[ R = \textrm{You get an A in the class} \] For each of the following 3 propositions, choose the equivalent logical statement.

You get an A in the class, but you do not do every exercise in the book.

(a) \(R \textrm{ IMPLIES } \textrm{ NOT } Q\)

INCORRECT! This would be like saying that the reason why you didn't do every exercise is because you got an A.

(b) \(R \textrm{ AND } \textrm{ NOT } P\)

INCORRECT! There is nothing in this proposition about what you get on the final exam.

(c) \(R \textrm{ AND } \textrm{ NOT } Q\)

CORRECT! Both \(R\) and \textrm{ NOT}\(Q\) happened.

(d) \(Q \textrm{ IMPLIES } R\)

INCORRECT! This is like saying you got an A because you did all of the exercises in the book.
You get an A on the final, you do every exercise in the book, and you get an A in the class.

(a) \(P \textrm{ AND } Q \textrm{ AND } R\)

CORRECT! The proposition says that all three of \(P,Q,R\) happen.

(b) \((P \textrm{ AND } Q) \textrm{ IMPLIES } R\)

INCORRECT! There is no implication here.

(c) \((P \textrm{ IFF } Q) \textrm{ AND } (Q \textrm{ IFF } R)\)

INCORRECT! This would be like saying that you get an A on the final exam exactly when you do every exercise in the book, and you do every exercise in the book exactly when you get an A in the course.

(d) \(P \textrm{ OR } Q \textrm{ OR } R\)

INCORRECT! This is saying that you did at least one of \(P,Q,R\).
To get an A in the class, it is necessary for you to get an A on the final exam.

(a) \(P \textrm{ AND } R\)

INCORRECT! This is saying that you get an A in the class and you get an A on the final exam.

(b) \(P \textrm{ IMPLIES } R\)

INCORRECT! This is saying that \(P\) is sufficient for \(R\), namely, if you get an A on the final exam, you'll get an A in the course.

(c) \(R \textrm{ IMPLIES } P\)

CORRECT! If you get an A in the course, then you know that you got an A on the final exam, that is, getting an A on the final exam was required.

(d) \(P \textrm{ IFF } R\)

INCORRECT! This is equivalent to saying that both (b) and (c) were correct answers, but (b) is incorrect.

In the next questions, you will be given some propositions along with a statement in logic that uses the propositions, and you must choose the English sentence(s) that most closely matches.

Define the following propositions:
\[ P = \textrm{Canada increases border security} \] \[ Q = \textrm{The U.S. increases border security} \]
Which of the following statements is equivalent to P IMPLIES Q?

(a) If Canada increases border security, so will the U.S.

ALMOST! This sentence is equivalent to P IMPLIES Q. However, (b) was also correct.

(b) Only when the U.S. increases border security will Canada do so.

ALMOST! This sentence is equivalent to P IMPLIES Q since "only when" immediately precedes the conclusion of an implication. However, (a) was also correct.

(c) Both (a) and (b) are correct.

CORRECT! Both (a) and (b) are equivalent to P IMPLIES Q.

(d) None of the above.

INCORRECT! At least one of (a) or (b) is correct.
Define the following propositions
\[ P = \textrm{The broadcast is successful} \] \[ Q = \textrm{The network is connected} \]
Which of the following is equivalent to P IMPLIES Q?

(a) The broadcast can't be successful without a connected network.

CORRECT! In other words, for the broadcast to be successful, a connected network is required. This is equivalent to P IMPLIES Q.

(b) A connected network is sufficient for a broadcast to be successful.

INCORRECT! This is the converse, that is, Q IMPLIES P.

(c) Both (a) and (b) are correct.

INCORRECT! At least one of (a) or (b) is incorrect.

(d) None of the above.

INCORRECT! At least one of (a) or (b) is correct.
Define the following propositions:
\[ P = \textrm{Visit the doctor} \] \[ Q = \textrm{Get a blood test} \] \[ R = \textrm{I am nervous} \]
Which of the following is equivalent to (P IMPLIES Q) IMPLIES R?

(a) To get a blood test done, I have to visit the doctor, which makes me nervous.

INCORRECT! This is equivalent to (Q IMPLIES P) AND (P IMPLIES R).

(b) I am nervous because I am going to visit the doctor to get a blood test done.

INCORRECT! This is more like (P AND Q) IMPLIES R.

(c) I get nervous whenever visiting the doctor requires getting a blood test done.

CORRECT! "Visiting the doctor requires getting a blood test done" is equivalent to P IMPLIES Q. Whenever P IMPLIES Q, I get nervous, so (P IMPLIES Q) IMPLIES R.

(d) None of the above.

INCORRECT! One of the above is correct.

In the next question, you will be given a statement in logic, and you must pick which answer is equivalent to it.

NOT((P AND Q) IMPLIES NOT(R)) AND (Q XOR ((NOT(Q)) OR (P AND NOT(P))))

(a) R IMPLIES (P OR Q)

INCORRECT! They do not evaluate to the same value when P=T, Q=T, R=F.

(b) P XOR (Q AND NOT(R))

INCORRECT! They do not evaluate to the same value when P=T, Q=F, R=T.

(c) Q OR (P AND R)

INCORRECT! They do not evaluate to the same value when P=F, Q=T, R=F.

(d) R AND (P AND Q)

CORRECT! It can be proven using a truth table, or by simplifying the statement using deMorgan's Laws and some simple logical equivalences.

The next question has no special instructions.

Some people are uncomfortable with the idea that from a false hypothesis you can prove everything, and instead of having P IMPLIES Q be true when P is false, they want P IMPLIES Q to be false when P is false. This would lead to IMPLIES having the same truth table as what propositional connective?

(a) XOR

INCORRECT! In the truth table of XOR, the row corresponding to \(P=Q=T\) has value F.

(b) OR

INCORRECT! In the truth table of OR, the row corresponding to \(P=F\) and \(Q=T\) has value T.

(c) IFF

INCORRECT! In the truth table of IFF, the row corresponding to \(P=Q=F\) has value T.

(d) AND

CORRECT! The truth table would have a T in the row corresponding to \(P=Q=T\), and F in all other rows.

Found an error? Send us an email

Lecture 1

If we know that \(x=0\), then what do we know about the value of \(xy\)?

If we know that \(x \neq 0\), then what do we know about the value of \(xy\)?

If we know that \(xy = 0\), then what do we know about the value of \(x\)?

If we know that \(xy \neq 0\), then what do we know about the value of \(x\)?

You get an A in the class, but you do not do every exercise in the book.

You get an A on the final, you do every exercise in the book, and you get an A in the class.

To get an A in the class, it is necessary for you to get an A on the final exam.

Define the following propositions:

Which of the following statements is equivalent to P IMPLIES Q?

Define the following propositions

Which of the following is equivalent to P IMPLIES Q?

Define the following propositions:

Which of the following is equivalent to (P IMPLIES Q) IMPLIES R?

NOT((P AND Q) IMPLIES NOT(R)) AND (Q XOR ((NOT(Q)) OR (P AND NOT(P))))

Some people are uncomfortable with the idea that from a false hypothesis you can prove everything, and instead of having P IMPLIES Q be true when P is false, they want P IMPLIES Q to be false when P is false. This would lead to IMPLIES having the same truth table as what propositional connective?