Discrete-math 1

1a

Prove or disprove: (A \to B) \to (B \to A) \equiv A \lor \neg B

F \equiv (A \to B) \to (B \to A)

$A$	$B$	$A \to B$	$B \to A$	$A \lor \neg B$	$F$
0	0	1	1	1	1
0	1	1	0	0	0
1	0	0	1	1	1
1	1	1	1	1	1

⟹ (A \to B) \to (B \to A) \equiv A \lor \neg B

1b

Prove or disprove: p \to q \equiv \neg q \to \neg p

$p$	$q$	$p \to q$	$\neg q \to \neg p$
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

⟹ p \to q \equiv \neg q \to \neg p

1c

Prove or disprove: (p \leftrightarrow q) \leftrightarrow (\neg q \leftrightarrow \neg p) is a tautology

F \equiv (p \leftrightarrow q) \leftrightarrow (\neg q \leftrightarrow \neg p)

$p$	$q$	$p \leftrightarrow q$	$\neg q \leftrightarrow \neg p$	$F$
0	0	1	1	1
0	1	0	0	1
1	0	0	0	1
1	1	1	1	1

⟹ F - tautology

1d

Prove or disprove: (p \lor q) \land (p \lor r) \equiv p \land (q \lor r)

F \equiv (p \lor q) \land (p \lor r)

G \equiv p \land (q \lor r)

$q$	$r$	$p \lor q$	$p \lor r$	$q \lor r$	$F$
0	0	0	0	0	0
0	1	0	1	1	0
1	0	1	0	1	0
1	1	1	1	1	1

⟹ (p \lor q) \land (p \lor r) \neq p \land (q \lor r)

2a

Prove: \neg (p \leftrightarrow q) \equiv (p \land \neg q) \lor (q \land \neg p)

\neg (p \leftrightarrow q) \equiv \neg ((p \to q) \land (q \to p)) \equiv \neg ((\neg p \lor q) \land (\neg q \lor p)) \equiv

\neg (\neg p \lor q) \lor \neg (\neg q \lor p) \equiv (p \land \neg q) \lor (q \land \neg p)

2b

Prove: (\neg p \to (q \land \neg r)) \lor (p \land q) \equiv p \lor (q \land \neg r)

(\neg p \to (q \land \neg r)) \lor (p \land q) \equiv (p \lor (q \land \neg r)) \lor (p \land q) \equiv p \lor ((q \land \neg r) \lor (p \land q)) \equiv

p \lor (q \land (\neg r \lor p)) \equiv (p \lor q) \land (p \lor (\neg r \lor p)) \equiv

(p \lor q) \land (p \lor \neg r) \equiv p \lor (q \land \neg r)

2c

Prove: \neg (p \to q) \equiv p \land \neg q

\neg (p \to q) \equiv \neg (\neg p \lor q) \equiv p \land \neg q

3a

If Eran is tired, he is upset.
When Eran is not upset, he is not tired.

A \equiv Eran is tired

B \equiv Eran is upset

1. A \to B \equiv \neg A \lor B

2. \neg B \to \neg A \equiv B \lor \neg A \equiv \neg A \lor B

⟹ 1. \equiv 2.

3b

If Eyal is happy, Anat is tall; and if Anat is tall, Haggai is cute.
If Eyal is happy, Haggai is cute.

A \equiv Eyal is happy

B \equiv Anat is tall

C \equiv Haggai is cute

1. (A \to B) \land (B \to C)

2. A \to C

$A$	$B$	$C$	$A \to B$	$B \to C$	$1.$	$2.$
0	1	0	1	0	0	1

⟹ 1. \neq 2.

3c

If I am vegan, then I eat quinoa and do not eat shawarma.
I do not eat quinoa only if I am not vegan, and I also do not eat shawarma
if I am vegan.

A \equiv I am vegan

B \equiv I eat quinoa

C \equiv I eat shawarma

1. (A \to B) \land (A \to \neg C)

2. (\neg B \to \neg A) \land (A \to \neg C)

Conditional law: A \to B \equiv \neg B \to \neg A

⟹ 1. \equiv 2.

4

The next exercise deals with cards that have a symbol on both sides—an English
letter on one side and a natural number on the other. Four cards are placed on the
table, showing the symbols A, P, 2, and 3. Which cards should be flipped to check
the statement ”If there is one of the letters AEIOU on one side of the card, then on
the other side, there is an even number”? Justify well (why the cards you suggested
need to be flipped, and why the other cards do not need to be checked).

A \equiv There is a letter A,E,I,O or U on the one side of the card

B \equiv There is an even number on the other side of the card

Statement: F \equiv A \to B

If there is a letter A on one side, then on the other is a natural number. If it's even, the statement holds, if not, the statement is false, thus we have to flip this card.
If there is a letter P on one side, then on the other is a natural number, if it's odd, the statement holds, if it's even, the statement still holds, thus we don't have to flip that card.
If there is a number 2 on one side, then on the other is a letter. If it's one of A,E,I,O or U, the statement holds, if it's not, the statement still holds, thus we don't have to flip this card.
If there is a number 3 on one side, then on the other is a letter. If it's not one of A,E,I,O or U, the statement holds, if it is, the statement is false, thus we have to flip this card.

C \equiv If there is a letter A on one side of the card, then there is an even number on the other

D \equiv If there is a number 3 on one side of the card, then there is a letter A,E,I,O or U on the other

F \to (C \land \neg D) or in other words, (\neg C \lor D) \to \neg F

We have to flip the card with a letter A and the card with a number 3

5a

If I am tired or hungry, then I am irritable.
If I am not irritable, then I am not tired.
Conclusion: I am tired if and only if I am irritable.

A \equiv I am tired

B \equiv I am hungry

C \equiv I am irritable

1. (A \lor B) \to C

2. \neg C \to \neg A

Conclusion: (1. \land 2.) \to (A \leftrightarrow C)

$A$	$B$	$C$	$1.$	$2.$	$1. \land 2.$	$A \leftrightarrow C$	$Conclusion$
0	1	1	1	1	1	0	0

⟹ Conclusion is incorrect

Alternative proof:

If I am irritable, I can just be hungry, but not tired. Contradiction with the conclusion.

⟹ Conclusion is incorrect

5b

If the sun is shining, then all the roosters are crowing.
If my rooster, Kuki, is crowing, then the sun is shining.
Conclusion: The sun shines if and only if all the roosters are crowing

A \equiv The sun is shining

B \equiv All the roosters are crowing

C \equiv My rooster, Kuki, is crowing

Obvious implication: B \to C

1. A \to B

2. C \to A

Conclusion: (1. \land 2.) \to (A \leftrightarrow B)

Lines that are crossed out are contradictions to the obvious implication,

and thus do not affect the result

$A$	$B$	$C$	$1.$	$2.$	$1. \land 2.$	$A \leftrightarrow B$	$Conclusion$
0	0	0	1	1	1	1	1
0	0	1	1	0	0	1	1
0	1	0	1	1	1	0	0
0	1	1	1	0	0	0	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	0	1
1	1	0	1	1	1	1	1
1	1	1	1	1	1	1	1

⟹ Conclusion is correct

Alternative proof:

If all the roosters are crowing, then my rooster Kuki is crowing, then the sun is shining.

⟹ Conclusion is correct

Let p, q be two statements such that the statement p → q has the value ”true.” In
this case, we say that p is a sufficient condition for q, and q is a necessary condition
for p. Formalize each of the following sections using appropriate predicates. In all
sections, the ”world” is the natural numbers; there is no need to state this.

Let us define the predicates:

P (N) \equiv number N is prime

E (N) \equiv number is even

G (N, M) \equiv N > M

D (N, M) \equiv M ∣ N (the ∣ character is a "divides" relation, in this case "M divides N")

6a

For every natural number n, the statement ”the number n is prime” is a sufficient condition for ”the number n is odd.”

\forall N : P (N) \to \neg E (N)

6b

For every natural number n, the statement ”the number n is prime and greater than 2” is a sufficient and necessary condition for ”the number n is odd.”

\forall N : (P (N) \land G (N, 2)) \leftrightarrow \neg E (N)

6c

For every natural number n, the statement ”the number n is divisible by 4” is a sufficient condition for ”the number n is even.”

\forall N : D (N, 4) \to E (N)

6d

For every natural number n, the statement ”the number n is even” is a necessary condition for ”the number n is divisible by 4.”

\forall N : D (N, 4) \to E (N)

$A$	$B$	$C$	$1.$	$2.$	$1. \land 2.$	$A \leftrightarrow B$	$Conclusion$
0	0	0	1	1	1	1	1
0	0	1	1	0	0	1	1
0	1	0	1	1	1	0	0
0	1	1	1	0	0	0	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	0	1
1	1	0	1	1	1	1	1
1	1	1	1	1	1	1	1

$A$	$B$	$C$	$1.$	$2.$	$1. \land 2.$	$A \leftrightarrow B$	$Conclusion$
0	0	0	1	1	1	1	1
0	0	1	1	0	0	1	1
0	1	0	1	1	1	0	0
0	1	1	1	0	0	0	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	0	1
1	1	0	1	1	1	1	1
1	1	1	1	1	1	1	1

$A$	$B$	$C$	$1.$	$2.$	$1. \land 2.$	$A \leftrightarrow B$	$Conclusion$
0	0	0	1	1	1	1	1
0	0	1	1	0	0	1	1
0	1	0	1	1	1	0	0
0	1	1	1	0	0	0	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	0	1
1	1	0	1	1	1	1	1
1	1	1	1	1	1	1	1