Lesson test: Equivalence and normal forms

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Equivalence and normal forms

1.[2p]
$\neg (P \land Q)$ is equivalent to

$\neg P \lor \neg Q$

Correct

$\neg P \land \neg Q$

The answer is: $\neg P \vee \neg Q$

$P \lor \neg Q$

The answer is: $\neg P \vee \neg Q$

$\neg (P \lor Q)$

The answer is: $\neg P \vee \neg Q$

2.[2p]
In a normal form, what is an atom or the negation of an atom called? One word.

CorrectNot quite: literal

3.[3p]
$\neg (P \to Q)$ is equivalent to

$P \land \neg Q$

Correct

$\neg P \lor Q$

The answer is: $P \wedge \neg Q$

$\neg P \land Q$

The answer is: $P \wedge \neg Q$

$Q \to P$

The answer is: $P \wedge \neg Q$

4.[3p]
Which sets of connectives are functionally complete?

Select all that apply

$\neg$ and $\land$

Correct

$\neg$ and $\to$

Correct

NAND on its own

Correct

$\land$ and $\lor$

The answer is: $\neg$ and $\wedge$, $\neg$ and $\rightarrow$, NAND on its own

5.[2p]
How many of the sixteen binary truth functions are functionally complete on their own?

CorrectNot quite: 2

6.[2p]
A formula is in conjunctive normal form when it is

a conjunction of disjunctions of literals

Correct

a disjunction of conjunctions of literals

The answer is: a conjunction of disjunctions of literals

built only from $\neg$ and $\land$

The answer is: a conjunction of disjunctions of literals

free of every negation

The answer is: a conjunction of disjunctions of literals

7.[3p]
To build the disjunctive normal form from a truth table, you write one conjunction for

each row where the formula is true, using the literals that describe that row

Correct

each row where the formula is false, negating every literal

The answer is: each row where the formula is true, using the literals that describe that row

each atom in the formula

The answer is: each row where the formula is true, using the literals that describe that row

each clause of the conjunctive normal form

The answer is: each row where the formula is true, using the literals that describe that row

8.[2p]
Replacing a subformula by an equivalent one can change the truth value of the whole formula.

True

The answer is: False

False

Correct

9.[3p]
Match each law to its statement.

Implication
Contraposition
Absorption
Double negation

$P \to Q \equiv \neg Q \to \neg P$
$P \to Q \equiv \neg P \lor Q$
$\neg \neg P \equiv P$
$P \lor (P \land Q) \equiv P$

Show the answer

Implication: $P \to Q \equiv \neg P \lor Q$ Contraposition: $P \to Q \equiv \neg Q \to \neg P$ Absorption: $P \lor (P \land Q) \equiv P$ Double negation: $\neg \neg P \equiv P$

1.[2p] ¬(P∧Q) is equivalent to

2.[2p] In a normal form, what is an atom or the negation of an atom called? One word.

3.[3p] ¬(P→Q) is equivalent to

4.[3p] Which sets of connectives are functionally complete?

5.[2p] How many of the sixteen binary truth functions are functionally complete on their own?

6.[2p] A formula is in conjunctive normal form when it is

7.[3p] To build the disjunctive normal form from a truth table, you write one conjunction for

8.[2p] Replacing a subformula by an equivalent one can change the truth value of the whole formula.

9.[3p] Match each law to its statement.

1.[2p]
$\neg (P \land Q)$ is equivalent to

2.[2p]
In a normal form, what is an atom or the negation of an atom called? One word.

3.[3p]
$\neg (P \to Q)$ is equivalent to

4.[3p]
Which sets of connectives are functionally complete?

5.[2p]
How many of the sixteen binary truth functions are functionally complete on their own?

6.[2p]
A formula is in conjunctive normal form when it is

7.[3p]
To build the disjunctive normal form from a truth table, you write one conjunction for

8.[2p]
Replacing a subformula by an equivalent one can change the truth value of the whole formula.

9.[3p]
Match each law to its statement.