A Course in Discrete Math/Chapter 1 Logic/Homework set 1

Exercise 1

Identify which of these sentences are propositions.

1. Every square is also a circle.
2. x+1=2.
3. Oh hello!
4. Help me with the door, please.
5. There's no business like show business.

Exercise 2

Below is an association between propositional variables and specific propositions.

r: You are root.

g: You are in the management user group.

i: You have privilege to install programs.

m: You have a gym membership.

d: You paid the gym day-pass fee.

u: You may use the gym.

Translate the English sentences below into symbolic form, using the association above.

1. You do not have privilege to install programs unless you are root.
2. You have installation privilege only if you are root or are in the management user group.
3. If you are root then you have installation privilege, but must not be in the management user group.
4. To use the gym you must pay the day-pass fee, unless you have a gym membership.

Exercise 3

With the same meanings of the propositional variables r, g, i, m, d, and u, translate the following symbolic expressions into natural English.

1. $r\oplus (\neg g)$
2. $i\leftrightarrow r$
3. $\neg u\land \neg m$

Exercise 4

Determine whether the following conditionals are true.

1. "If 1+1 = 2 then 2+2 = 4."
2. "If 1+1 = 1 then 2+2 = 4."
3. "If 1+1 = 1 then 2+2 = 2."
4. "2 > 3 if and only if 0 > 1."

Exercise 5

Make up your own symbol key to symbolize the following propositions.

The choice of letter for each variable is not important, although it is standard to use a letter that is at least somewhat reflective of the proposition's content.

What is important, is that the meaning associated with each variable should not itself contain any propositional operators.

1. To take calculus you must take algebra and geometry.
2. To get the job, it is necessary but not sufficient to meet the educational qualifications.

Exercise 6

Let n be any natural number, $1\leq n$. Argue that

$\bigwedge _{i=1}^{n}p_{i}$

is true only on the row of the truth table where all variables $p_{1},p_{2},\dots ,p_{n}$ are all assigned to T.

Note: As this course progresses, we will develop proof writing skills. At this early stage, you are not expected to give fully professional proofs because we haven't yet developed that skill!

Therefore, your argument should be convincing, but it does not need to be formal in the way that we will require later in the course.

However, your argument should not be as simple as "$\bigwedge _{i=1}^{n}p_{i}$ just means that all the variables are true". It should be more like "If all the variables are assigned to T then ... (fill in this argument). But if some variable is not assigned to T then ... (fill in this argument)."