HW1 詳解

Question 1

問題1

page 16, Section 1.1 Exercise 34(f)

Construct a truth table for each of this compound proposition:
$(p \leftrightarrow q) \oplus (p \leftrightarrow \neg q)$

Construct a truth table for each of this compound proposition:
$(p \leftrightarrow q) \oplus (p \leftrightarrow \neg q)$

$p$	$q$	$\neg q$	$p↔q$	$p↔¬q$	$(p↔q)⊕(p↔¬q)$
T	T	F	T	F	T
T	F	T	F	T	T
F	T	F	F	T	T
F	F	T	T	F	T

Question 2

問題2

page 24, Section 1.2 Exercise 8

Express these system specifications using the propositions
$p$: “The user enters a valid password”,
$q$: “Access is granted”,
and $r$: “The user has paid the subscription fee”
and logical connectives (including negations).

“The user has paid the subscription fee, but does not enter a valid password.”
“Access is granted whenever the user has paid the subscription fee and enters a valid password.”
“Access is denied if the user has not paid the subscription fee.”
“If the user has not entered a valid password but has paid the subscription fee, then access is granted.”

Express these system specifications using the propositions
$p$: “The user enters a valid password”,
$q$: “Access is granted”,
and $r$: “The user has paid the subscription fee”
and logical connectives (including negations).

“The user has paid the subscription fee, but does not enter a valid password.”
“Access is granted whenever the user has paid the subscription fee and enters a valid password.”
“Access is denied if the user has not paid the subscription fee.”
“If the user has not entered a valid password but has paid the subscription fee, then access is granted.”

$r \wedge \neg p $
$(r \wedge p) \to q$
$\neg r \to \neg q$
$(\neg p \wedge r) \to q$

Express these system specifications using the propositions
$p$: “The user enters a valid password”,
$q$: “Access is granted”,
and $r$: “The user has paid the subscription fee”
and logical connectives (including negations).

“The user has paid the subscription fee$r$, but does not enter a valid password$\neg p$.”
“$q$Access is granted whenever the user has paid the subscription fee$r$ and $p$enters a valid password.”
“$\neg q$Access is denied if the user has not paid the subscription fee.$\neg r$”
“If $\neg p$the user has not entered a valid password but has paid the subscription fee$r$, then access is granted$q$.

$r \wedge \neg p $
$(r \wedge p) \to q$
$\neg r \to \neg q$
$(\neg p \wedge r) \to q$

Question 3

問題3

page 38, Section 1.3 Exercise 10(c)

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

\begin{eqnarray*} (p \rightarrow \neg q) \rightarrow (\neg p \rightarrow q) & \equiv & \neg (p \rightarrow \neg q) \lor (\neg p \rightarrow q ) & \text{by the condition-disjunction equivalence} \\ & \equiv & \neg (\neg p \lor \neg q) \lor (\neg \neg p \lor q) & \text{by the condition-disjunction equivalence}\\ & \equiv & ( p \land q) \lor ( p \lor q) & \text{by the double negation and DeMorgan's laws} \\ & \equiv & ( p \land q) \lor p \lor q & \text{by the associative law} \\ & \equiv & p \lor q & \text{by the absorbtion laws} \end{eqnarray*}

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

conditional-disjunction equivalence:
$p → q$ and $¬p ∨ q$ are logically equivalent.

\begin{eqnarray*} (p \rightarrow \neg q) \rightarrow (\neg p \rightarrow q) & \equiv & \neg (p \rightarrow \neg q) \lor (\neg p \rightarrow q ) & \text{by the condition-disjunction equivalence} \\ & \equiv & \neg (\neg p \lor \neg q) \lor (\neg \neg p \lor q) & \text{by the condition-disjunction equivalence}\\ & \equiv & ( p \land q) \lor ( p \lor q) & \text{by the double negation and DeMorgan's laws} \\ & \equiv & ( p \land q) \lor p \lor q & \text{by the associative law} \\ & \equiv & p \lor q & \text{by the absorbtion laws} \end{eqnarray*}

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

conditional-disjunction equivalence:
$p → q$ and $¬p ∨ q$ are logically equivalent.

\begin{eqnarray*} \color{cyan}{(p \rightarrow \neg q)} \rightarrow \color{OrangeRed}{(\neg p \rightarrow q)} & \equiv & \neg (p \rightarrow \neg q) \lor (\neg p \rightarrow q ) & \text{by the condition-disjunction equivalence} \\ & \color{gray}\equiv & \color{gray}{\neg (\neg p \lor \neg q) \lor (\neg \neg p \lor q)} &\color{gray}{ \text{by the condition-disjunction equivalence}}\\ & \color{gray}\equiv & \color{gray}{( p \land q) \lor ( p \lor q)} & \color{gray}{\text{by the double negation and DeMorgan's laws}} \\ & \color{gray}\equiv & \color{gray}{( p \land q) \lor p \lor q} & \color{gray}{\text{by the associative law}} \\ & \color{gray}\equiv & \color{gray}{p \lor q} & \color{gray}{\text{by the absorbtion laws}} \end{eqnarray*}

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

conditional-disjunction equivalence:
$p → q$ and $¬p ∨ q$ are logically equivalent.

\begin{eqnarray*} (p \rightarrow \neg q) \rightarrow (\neg p \rightarrow q) & \equiv & \neg (\color{cyan}p \rightarrow \color{orangered}{\neg q}) \lor (\color{cyan}{\neg p} \rightarrow \color{orangered}q ) & \color{gray}{\text{by the condition-disjunction equivalence}} \\ & \equiv & \neg (\neg p \lor \neg q) \lor (\neg \neg p \lor q) & \text{by the condition-disjunction equivalence}\\ & \color{gray}\equiv & \color{gray}{( p \land q) \lor ( p \lor q)} & \color{gray}{\text{by the double negation and DeMorgan's laws}} \\ & \color{gray}\equiv & \color{gray}{( p \land q) \lor p \lor q} & \color{gray}{\text{by the associative law}} \\ & \color{gray}\equiv & \color{gray}{p \lor q} & \color{gray}{\text{by the absorbtion laws}} \end{eqnarray*}

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

conditional-disjunction equivalence:
$p → q$ and $¬p ∨ q$ are logically equivalent.

DeMorgan's laws:

$\neg (p \wedge q) \equiv (\neg p) \vee (\neg q)$
$\neg (p \vee q) \equiv (\neg p) \wedge (\neg q)$

\begin{eqnarray*} (p \rightarrow \neg q) \rightarrow (\neg p \rightarrow q) & \color{gray}\equiv & \color{gray}{\neg (p \rightarrow {\neg q}) \lor (\neg p \rightarrow q )} & \color{gray}{\text{by the condition-disjunction equivalence}} \\ & \equiv & \color{limegreen}{\neg (\neg p \lor \neg q)} \lor (\color{salmon}{\neg \neg} p \lor q) & \color{gray}{\text{by the condition-disjunction equivalence}}\\ & \equiv & ( p \land q) \lor ( p \lor q) & \text{by the double negation and DeMorgan's laws}\\ & \color{gray}\equiv & \color{gray}{( p \land q) \lor p \lor q} & \color{gray}{\text{by the associative law}} \\ & \color{gray}\equiv & \color{gray}{p \lor q} & \color{gray}{\text{by the absorbtion laws}} \end{eqnarray*}

Use the conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not involve conditionals.
$(p \to \neg q) \to (\neg p \to q)$

Associative laws:
$(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)$
$(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)$.

Absorption laws:

$p ∨ (p ∧ q) ≡ p$
$ p ∧ (p ∨ q) ≡ p$

\begin{eqnarray*} (p \rightarrow \neg q) \rightarrow (\neg p \rightarrow q) & \color{gray}\equiv & \color{gray}{\neg (p \rightarrow {\neg q}) \lor (\neg p \rightarrow q )} & \color{gray}{\text{by the condition-disjunction equivalence}} \\ & \color{gray}\equiv & \color{gray}{\neg (\neg p \lor \neg q) \lor (\neg \neg p \lor q}) & \color{gray}{\text{by the condition-disjunction equivalence}}\\ & \equiv & ( p \land q) \lor ( p \lor q) & \color{gray}{\text{by the double negation and DeMorgan's laws}}\\ &\equiv & ( p \land q) \lor p \lor q & \text{by the associative law} \\ & \equiv & p \lor q & \text{by the absorbtion laws} \end{eqnarray*}

Question 4

問題4

page 58, Section 1.4 Exercise 28

Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives.

Something is not in the correct place.
All tools are in the correct place and are in excellent condition.
Everything is in the correct place and in excellent condition.
Nothing is in the correct place and is in excellent condition.
One of your tools is not in the correct place, but it is in excellent condition.

Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives.

Something is not in the correct place.
All tools are in the correct place and are in excellent condition.
Everything is in the correct place and in excellent condition.
Nothing is in the correct place and is in excellent condition.
One of your tools is not in the correct place, but it is in excellent condition.

let $R(x)$ be "$x$ is in the correct place",
let $E(x)$ be "$x$ is in excellent condition",
let $T(x)$ be "$x$ is a tool",
let the domain of discourse be all things

$\exists x ~ \neg R(x)$
$\forall x ~(T(x) \rightarrow (R(x) \land E(x)))$
$\forall x ~(R(x) \land E(x))$
$\forall x ~ \neg (R(x) \land E(x))$
$\exists x ~(T(x) \land \neg R(x) \land E(x))$

Question 5

問題5

page 58, Section 1.4 Exercise 30

Suppose the domain of the propositional function $P(x, y)$ consists of pairs $x$ and $y$, where $x$ is $1$, $2$, or $3$ and $y$ is $1$, $2$, or $3$. Write out these propositions using disjunctions and conjunctions.

$∃x \: P(x, 3)$
$∀y \: P(1, y)$
$∃y \: ¬P(2, y)$
$∀x \: ¬P(x, 2)$

Suppose the domain of the propositional function $P(x, y)$ consists of pairs $x$ and $y$, where $x$ is $1$, $2$, or $3$ and $y$ is $1$, $2$, or $3$. Write out these propositions using disjunctions and conjunctions.$(\vee,\wedge)$

$∃x \: P(x, 3)$
$∀y \: P(1, y)$
$∃y \: ¬P(2, y)$
$∀x \: ¬P(x, 2)$

$ P(1,3) \vee P(2,3) \vee P(3,3) $
$ P(1,1) \wedge P(1,2) \wedge P(1,3) $
$ \neg P(2,1) \vee \neg P(2,2) \vee \neg P(2,3) $
$ \neg P(1,2) \wedge \neg P(2,2) \wedge \neg P(3,2) $

Question 6

問題6

page 71, Section 1.5 Exercise 26

Let Q(x, y) be the statement “x + y = x − y.” If the domain for both variables consists of all integers, what are the truth values?

$Q(1, 1)$
$Q(2, 0)$
$∀y \: Q(1, y)$
$∃x \: Q(x, 2)$
$∃x∃y \: Q(x, y)$
$∀x∃y \: Q(x, y)$
$∃y∀x \: Q(x, y)$
$∀y∃x \: Q(x, y)$
$∀x∀y \: Q(x, y)$

Let Q(x, y) be the statement “x + y = x − y.” If the domain for both variables consists of all integers, what are the truth values?

$Q(1, 1)$
$Q(2, 0)$
$∀y \: Q(1, y)$
$∃x \: Q(x, 2)$
$∃x∃y \: Q(x, y)$
$∀x∃y \: Q(x, y)$
$∃y∀x \: Q(x, y)$
$∀y∃x \: Q(x, y)$
$∀x∀y \: Q(x, y)$

F
T
F
F
T
T
T
F
F

Let Q(x, y) be the statement “x + y = x − y.” If the domain for both variables consists of all integers, what are the truth values?

$Q(1, 1)$
$Q(2, 0)$
$∀y \: Q(1, y)$
$∃x \: Q(x, 2)$
$∃x∃y \: Q(x, y)$
$∀x∃y \: Q(x, y)$
$∃y∀x \: Q(x, y)$
$∀y∃x \: Q(x, y)$
$∀x∀y \: Q(x, y)$

F $\quad \because 1+1 \neq 1-1$
T $\quad \because 2+0 = 2-0$
F $\quad \because 1 \in y, 1+1 \neq 1-1$
F $\quad suppose \: that \: x+2 = x-2 \Rightarrow 0=-4 \text{ is not possible}$
T $\quad \because 2 \in x,\: 0 \in y,\: 2+0 = 2-0$
T $\quad set \: y = 0, \: x+0 = x-0$
T $\quad set \: y = 0, \: x+0 = x-0$
F $\quad x + y = x - y \Rightarrow y = 0$
F

Question 7

問題7

page 71, Section 1.5 Exercise 32(c)

Express the negation of the statement so that it immediately precede predicates.
$∃x∃y(Q(x, y) ↔ Q(y, x))$

Express the negation of the statement so that it immediately precede predicates.
$∃x∃y(Q(x, y) ↔ Q(y, x))$

$$\begin{eqnarray*} \neg \exists x \exists y (Q(x,y) \leftrightarrow Q(y,x)) & \equiv & \forall x \neg \exists y (Q(x,y) \leftrightarrow Q(y,x)) \\ & \equiv & \forall x \forall y \neg (Q(x,y) \leftrightarrow Q(y,x)) \\ & \equiv & \forall x \forall y (\neg Q(x,y) \leftrightarrow Q(y,x)) \end{eqnarray*}$$

Express the negation of the statement so that it immediately precede predicates.
$∃x∃y(Q(x, y) ↔ Q(y, x))$

DeMorgan's laws for quantifiers:

$\neg \forall x f(x) = \exists x \neg f(x)$
$\neg \exists x f(x) = \forall x \neg f(x)$

$$\begin{eqnarray*} \neg \exists x \exists y (Q(x,y) \leftrightarrow Q(y,x)) & \equiv & \forall x \neg \exists y (Q(x,y) \leftrightarrow Q(y,x)) \\ & \equiv & \forall x \forall y \neg (Q(x,y) \leftrightarrow Q(y,x)) \\ & \equiv & \forall x \forall y (\neg Q(x,y) \leftrightarrow Q(y,x)) \end{eqnarray*}$$

Question 8

問題8

page 82, Section 1.6 Exercise 6

Use rules of inference to show that the hypotheses
“If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on,”
“If the sailing race is held, then the trophy will be awarded,”
and “The trophy was not awarded” imply the conclusion “It rained.”

Use rules of inference to show that the hypotheses
“If it does not rain$\neg r$ or if it is not foggy$\neg f$, then the sailing race will be held$s$ and the lifesaving demonstration will go on$l$,”
“If the sailing race is held$s$, then the trophy will be awarded$t$,”
and “The trophy was not awarded”$\neg t$ imply the conclusion “It rained.”$r$

let $r$ be the proposition "It rains,"
let $f$ be the proposition "It is foggy,"
let $s$ be the proposition "The sailing race will be held,"
let $l$ be the proposition "The life saving demonstration will go on",
let $t$ be the proposition "The trophy will be awarded."

Step	Statement	Reason
1	$\neg t$	Hypothesis
2	$s \to t$	Hypothesis
3	$\neg s$	Modus tollens using (1) and (2)
4	$(\neg r \lor \neg f) \rightarrow (s \land l)$	Hypothesis
5	$(\neg(s \land l))\rightarrow \neg(\neg r \lor \neg f)$	Contrapositive of (4)
6	$(\neg s \lor \neg l)\rightarrow (r \land f)$	De Morgan's law and double negative
7	$\neg s \lor \neg l$	Addition, using (3)
8	$r \land f$	Modus ponens using (6) and (7)
9	$r$	Simplification using (8)

Use rules of inference to show that the hypotheses
“If $¬r$ or if $¬f$, then $s$ and $l$,”
“If $s$, then $t$,”
and $¬t$ imply the conclusion $r$

let $r$ be the proposition "It rains,"
let $f$ be the proposition "It is foggy,"
let $s$ be the proposition "The sailing race will be held,"
let $l$ be the proposition "The life saving demonstration will go on",
let $t$ be the proposition "The trophy will be awarded."

Premises:
$(\neg r \vee \neg f) \to (s \wedge l)$
$s→t$
$\neg t$

Step	Statement	Reason
1	$\neg t$	Hypothesis
2	$s \to t$	Hypothesis
3	$\neg s$	Modus tollens using (1) and (2)
4	$(\neg r \lor \neg f) \rightarrow (s \land l)$	Hypothesis
5	$(\neg(s \land l))\rightarrow \neg(\neg r \lor \neg f)$	Contrapositive of (4)
6	$(\neg s \lor \neg l)\rightarrow (r \land f)$	De Morgan's law and double negative
7	$\neg s \lor \neg l$	Addition, using (3)
8	$r \land f$	Modus ponens using (6) and (7)
9	$r$	Simplification using (8)