Chapter 1: The Foundations: Logic and Proofs

How many different truth tables of compound propositions are there that involve the propositional variables p and q.

Show that if p,q and r are compound propositions such that p and qare logically equivalent and q and rare logically equivalent, then pand r are logically equivalent.

Given the Prolog facts in Example 28, what would Prolog

return when given these queries?

a) ?enrolled(kevin,ee222)

b) ?enrolled(kiko,math273)

c) ?instructor(grossman,X)

d) ?instructor(X,cs301)

e) ?teaches(X,kevin)

Suppose that Prolog facts are used to define the predicates mother $\left(M,Y\right)$ and father $\left(F,X\right)$,which represent that Mis the mother of Yand Fis the father of X, respectively. Give a Prolog rule to define the predicate sibling $\mathbf{(}\mathit{X}\mathbf{,}\mathit{Y}\mathbf{)}$, which represents that Xand Yare siblings (that is, have the same mother and the same father).

The following sentence is taken from the specification of a telephone system: “If the directory database is opened, then the monitor is put in a closed state, if the system is not in its initial state.” This specification is hard to understand because it involves two conditional statements. Find an equivalent, easier-to-understand specification that involves disjunctions and negations but not conditional statements.

Suppose that Prolog facts are used to define the predicates mother$\left(M,Y\right)$and father$\left(F,X\right)$which represent that Mis the mother of Yand Fis the father of X, respectively. Give a Prolog rule to define the predicate grandfather $\mathbf{(}\mathit{X}\mathbf{,}\mathit{Y}\mathbf{)}$,which represents that Xis the grandfather of Y. [Hint: You can write a disjunction in Prolog either by using a semicolon to separate predicates or by putting these predicates on separate lines.]

How many of the disjunctions $\mathbf{p}\mathbf{\vee }\mathbf{\neg }\mathbf{q}\mathbf{,}\mathbf{}\mathbf{\neg }\mathbf{p}\mathbf{\vee }\mathbf{q}\mathbf{,}\mathbf{}\mathbf{q}\mathbf{\vee }\mathbf{r}\mathbf{,}\mathbf{}\mathbf{q}\mathbf{\vee }\mathbf{\neg }\mathbf{r}$and $\mathbf{\neg }\mathbf{q}\mathbf{\vee }\mathbf{\neg }\mathbf{r}$can be made simultaneously true by an assignment of truth values to p,q and r ?

Let $\mathit{P}\left(x\right)\mathbf{,}\mathit{Q}\left(x\right)\mathbf{,}$and$\mathit{R}\left(x\right)$be the statements “xis a professor,” “xis ignorant,” and “xis vain,” respectively. Express each of these statements using quantifiers; logical connectives; and$\mathit{P}\left(x\right)\mathbf{,}\mathit{Q}\left(x\right)\mathbf{,}$and$\mathit{R}\left(x\right)$where the domain consists of all people.

a) No professors are ignorant.

b) All ignorant people are vain.

c) No professors are vain.

d) Does (c) follow from (a) and (b)?

How many of the disjunctions $\mathbf{p}\mathbf{\vee }\mathbf{\neg }\mathbf{q}\mathbf{\vee }\mathbf{s}\mathbf{,}\mathbf{}\mathbf{\neg }\mathbf{p}\mathbf{\vee }\mathbf{\neg }\mathbf{r}\mathbf{\vee }\mathbf{s}\mathbf{,}\mathbf{}\mathbf{\neg }\mathbf{p}\mathbf{\vee }\mathbf{q}\mathbf{\vee }\mathbf{\neg }\mathbf{s}\mathbf{,}\mathbf{}\mathbf{q}\mathbf{\vee }\mathbf{r}\mathbf{\vee }\mathbf{\neg }\mathbf{s}\mathbf{,}\mathbf{}\mathbf{\neg }\mathbf{p}\mathbf{\vee }\mathbf{q}\mathbf{\vee }\mathbf{\neg }\mathbf{s}\mathbf{,}\mathbf{p}\mathbf{\vee }\mathbf{r}\mathbf{\vee }\mathbf{s}\mathbf{,}$and $\mathbf{p}\mathbf{\vee }\mathbf{r}\mathbf{\vee }\mathbf{\neg }\mathbf{s}\mathbf{,}$ can be made simultaneously true by an assignment of truth values to p,q,r and s?

Use a truth table to verify the distributive law.$\mathbf{p}\mathbf{\wedge }\left(q\vee r\right)\mathbf{\equiv }\mathbf{(}\mathbf{p}\mathbf{\wedge }\mathbf{q}\mathbf{)}\mathbf{\vee }\mathbf{(}\mathbf{p}\mathbf{\wedge }\mathbf{r}\mathbf{)}$