1.1
Construct a truth table for each, decide whether:
- it is a tautology
- it is satisfiable
(a)
| T | T | T | T | T | T | T | T | F |
| T | T | F | T | F | F | F | T | F |
| T | F | T | F | T | T | T | T | F |
| T | F | F | F | T | T | T | T | F |
| F | T | T | F | T | T | T | T | F |
| F | T | F | F | T | F | T | T | F |
| F | F | T | F | T | T | T | T | F |
| F | F | F | F | T | T | T | T | F |
not a tautology or satisfiable.
title:
Correct conclusion.(b)
| T | T | T | F | T | F | F | F | F | F |
| T | T | F | F | T | F | F | T | T | T |
| T | F | T | T | T | F | F | F | F | F |
| T | F | F | T | T | F | F | F * | F | F |
| F | T | T | F | F | T | T | T | T | F |
| F | T | F | F | F | T | T | T | T | F |
| F | F | T | T | T | F | T | T | T | F |
| F | F | F | T | T | F | T | T | T | F |
is not a tautology but is satisfiable.
title:
Correct conclusion.
Made a mistake computing TFF, ended up with F as final value instead of T.
Value marked with * should have been true.1.2
Proposition (Sheffer stroke) is true when or are both false.
(a) Write a truth table
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
title:
Correct truth table.(b) Show is logically equivalent to
| T | T | F | T | F | T |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | T | F | T | T |
They have the same truth values in all possible scenarios hence are logically equivalent.
title:
Correct truth table.1.3
At most, how many of the these:
can be made simultaneously true by an assignment of values to , and ?
| T | T | T | T | T | T | T | F |
| T | T | F | T | T | T | T | T |
| T | F | T | T | F | T | F | T |
| T | F | F | T | F | F | T | T |
| F | T | T | F | T | T | T | F |
| F | T | F | F | T | T | T | T |
| F | F | T | T | T | T | F | T |
| F | F | F | T | T | F | T | T |
They are all simulatenously true when and are true and is false.
title:
Correct truth table.
Initially copied down the heading wrong, instead writing
$$
p \lor \neg q,\hspace{12px}
\neg p\land q,\hspace{12px}
q \lor r,\hspace{12px}
q\lor \neg r,\hspace{12px}
\neg q \land \neg r
$$1.4
Use truth tables to verify the following:
(a)
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | F | F | F |
| F | F | T | T | T | T |
title:
Correct truth table.(b)
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | T | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
title:
Correct truth table.(c)
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
1.5
Use de Morgan’s laws to find the negation of each of the following statements:
(a) Jan is rich and happy.
- It is not the case that Jan is rich and happy.
- It is the case that Jan is either not rich or not happy.
Jan is either not rich or not happy.
(b) Carlos will swim or run tomorrow.
- It is not the case Carlos will swim or run tomorrow.
- It is the case that Carlos will not swim and not run tomorrow.
Carlos will not swim or run tomorrow.
(c) Mei walks or takes the bus to class.
- It is not the case that Mei walks or takes the bus to class.
- It is the case that Mei does not walk to class and does not take the bus to class.
Mei neither walks or takes the bus to class.
(d) Ibrahim is smart and hard working.
- It is not the case Ibrahim is smart and hard working.
- It is the case that Ibrahim is not smart or is not hard working.
Ibrahim is either not smart or not hard working.
title:
Correct statements.1.6
Formalise the following collection of statements, decide whether it is consistent or not.
If Joe is at home but Sue isn’t, Mum is nervous. Neither Bob nor Sue are at home. Joe is at home and Mum is not nervous.
Let be that Joe is at home. Let be that Sue is at home. Let be that Bob is at home. Let be that mum is nervous.
Hence,
Since , then both and are false. Since , then is true and is false.
So, subsitute into first formula:
Hence the collection of statements is not consistent since mum must be nervous if Joe is at home and Sue isn’t.
title:
Correct conclusion.
Alternative solution is to compute the entire truth table to see that none of the rows are consistent.1.7
Raymond Smullyan posed many puzzles about an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves, who always lie. Here is one his puzzles:
You encounter two people, A and B. What are A and B if A says “B is a knight” and B says “The two of us are opposite types”?
Let be the case that A is a knight. Let be the case that B is a knight.
- B is a knight if and only if A is telling the truth and a knight. ()
- A and B are opposite types if and only if B is telling the truth and a knight. ()
| T | T | F | T | F |
| T | F | T | F | F |
| F | T | T | F | T |
| F | F | F | T | T |
The formula is satisfied by the condition that both A and B are knaves.
title:
Correct outcome.
Originally used $\rightarrow$ instead of $\iff$, must be careful to use the correct implication.1.8
Translate these statements into English, where is “x is a rabbit” and is “x hops”, and the domain consists of all animals.
(a)
For all of , if is a rabbit then hops.
(b)
For all of , is a rabbit and hops.
(c)
There exists that if it is a rabbit then it hops.
(c)
There exists that is a rabbit and hops.
title:
Correct statements.
We can make these less formal like so:
> Every rabbit hops.
> All animals are rabbits and they all hop.
> There is an animal such that if it is a rabbit then it hops.
> There is a hopping rabbit.1.9
For each of these quantified statements, find a domain for which the statement is true, and a domain for which the statement is false:
(a) Everyone is studying discrete mathematics
This statement is true for the students studying computer science. This statement is not true for the people not studying anything.
(b) Everyone is older than 11 years.
This statement is true for the people in university. This statement is false for all people living on Earth.
(c) Every two people have the same mother.
This statement is true for all children of any particular mother. This statement is false for everyone on Earth.
(d) No two different people have the same grandmother.
This statement is true for me and my friends. This statement is false for everyone living in the UK.
title:
Correct statements.
Initially overcomplicated the question and included "domain of" in statements.1.10
Show by induction that, for every positive integer :
Basis case: Ensure that it works when .
Inductive step: We can assume that it works when .
We can try to see whether it works when :
Since the basis and inductive step were successful, by mathematical induction, the formula above applies for every positive integer, .
title:
Correctly follows Mathematical Induction.1.11
title:
### Not on exam!{
"url":"[FC1EX1 Tutorial Exercises.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1EX1%20Tutorial%20Exercises.pdf)",
"page":[2],
"scale":1.2,
"rect":[70, 530, 225, 470]
}