Introduction to Logic

• Logic is a formal language used to represent a set of state
• A convenient abstraction for dealing with many states
• Regardless of whether there's a natural notion of "near" or not (i.e. not a metric space), we can use logic to group different states together
• For example:
• I have a laptop ⇒ Includes any brand and model
• There is a laptop on the table ⇒ Can be at any position on the table.

Logic Definitions

• Interpretation Assignment of values to all variables
• Model An interpretation (assignment of values) that satisfies the constraints
  • Often we don't just want to find a model, but we want to know what is true in all mdoels.
• Proposition A statement that is true or false in each interpretation

• The formal language representation and reasoning system is made up of:
  • Syntax describes what sentences are legal
  • Semantics specified the meanings of symbols
  • Atoms are symbols, starting with a lowercase letter
  • Definite Clause is an atom or rule of the form Atom $\Leftarrow$ symbol
  • Knowledge Base is a set of definite clauses. A knowledge base is true iff every definite clause within it is true in every model (interpretation; assignment)

Syntax of Propsitional Logic

Complex propositions (sentences) can be built from simpler propositions using logical connectives, such as

• Brackets ()
• Negation $\neg$
• And; Conjunction $\wedge$
• Or; Disjunction $\vee$
• Implication $\Rightarrow$
• Biconditional/Equivalence $\Leftrightarrow$

Model Example

For each $I_n$ describe whether it is a model of the knowledge base

For $I_1$ we have p=TRUE, q=TRUE, r=TRUE and s=TRUE

Since each clause is true, $I_1$ is a model of the knowledge base $KB$

For $I_2$ we have p=FALSE, q=FALSE, r=FALSE, s=FALSE

Since not every clause of $I_2$ is true, this is not a model of the knowledge base $KB$

For $I_3$ we have p=TRUE, q= TRUE, r=FALSE, s=FALSE

Since not every clause of $I_3$ is true, this is not a model of the knowledge base $KB$

Conjunctive Normal Form (CNF)

A conjunction of disjunctions

• CNF statements are statements of the form $(\neg A \vee B)\wedge(C \vee D)\wedge(E \vee F)$
• Suppose we have the statement $(A \vee B)\Rightarrow(C \Rightarrow D)$ that we want to convert to CNF.
• To do this, we follow three steps

1. Eliminate the arrows, using the rule $A\Rightarrow B \equiv \neg A \vee B$

2. Drive in the negations

3. Distribute OR over AND

Exercise 5.1

Mr Jones finds three trunks A, B and C in a cave. Based on studying the history of where these trunks came about, he knows that one trunk contains gold while two are empty. On the wall of the cave he found three clues: "A is empty", "B is empty" and "gold is in B". From studying the historical social norm of the villages around the cave, Mr Jones knows that only one of the clues is true, while the other two are false. Which trunk has the gold?

Hint: Break down the problem into the following steps

1. Convert to atoms (symbols that we want to evaluate the truth of)
2. Build logical statements using atoms
3. Convert to Conjunctive Normal Form
4. Evaluate the CNF sentences

We want to encode the clauses (atoms/rules in the problem) that are true in the intended interpretation by axiomatizing the domain.

1. Associate an atom with the situation we wish to validate (i.e., gold in trunk)
2. Encode Mr Jones’ knowledge of the situation into a set of logical sentences
3. Use these sentences to determine if there is a solution, where one of the chests is guaranteed to contain gold.

We begin by associating a variable for each of the trunks containing gold.

Then, $\neg A$ means that Trunk A does not contain gold.

Encode Mr Jones' knowledge

One trunk contains gold, while the other two are empty.

• $(A\wedge \neg B \wedge \neg C)$ translates to trunk A contains gold, while trunk B and C are empty.
• $(\neg A \wedge B \wedge \neg C)$ translates to trunk B has gold while the other two are empty.
• $(\neg A \wedge \neg B \wedge C)$ translates to trunk C has gold while the other two are empty.
• We have essentially enumerated all possible outcomes of this statement

Additional Clues

Additionally, Mr Jones knows of three clues, but additionally knows that only one of the clues is true, with the other two being false. We also want to encode this knowledge using logic. We know that the three clues were given as:

We begin by representing the three clues as $\neg A, \neg B, B$ respectively. Since Mr Jones knows that only one of these are true, we now need to consider each possibility to form our second logical sentence.

Simplifying the Problem

Simplifying the Second Sentence

1. Through the elimination of double negatives, we get

2. We know that $X\wedge\neg X=\text{False}$, so applying this we get:

3. We additionally know that $A\wedge A=A$:

4. Additionally, we know that $\text{False}\wedge A=A$

5. By the distributivity law, we know that the above statement is equivalent to

6. We know that $(\neg X \wedge X) = T$

Therefore, to satisfy $S_2, A$ must be true (that is, the gold is in trunk A). However, we are not done at this point. We need to check the combination of truth values for A, B and C that makes $S_1$ true. If we didn't do this, that means that there is a possibility that the gold is in trunk A, but it is also in one of the other trunks, violating our rule.

Rule Validation

We can perform the validation of rule $S_1$ through the construction of a truth table.

While $S_1$ looks difficult to compute, remember what it actually represents – It’s true when only one of $A, B, C$ are true. Since $A=T, B=F, C=F$ is the only row in which both $S_1$ and $S_2$ are true, we can guarantee that the gold is only in trunk A.

Exercise 5.2

Are the following entailments correct? Please provide the proof.

1. $(A\wedge B)\models (A \Leftrightarrow B)$
2. $(A\Leftrightarrow B) \models (A \wedge B)$

Hint: When we are asked to determine if an entailment is correct (or holds, or is true), we can convert the entailment into an implication and check if the implication is valid. Checking whether or not the implication is valid means solving a validity problem. Remember that a sentence is valid when very combination of variable assignments in the sentence causes it to be true

Exercise 5.2a

• We can convert the entailment $(A\wedge B)\models(A\Leftrightarrow B)$ to an implication of the form $A \wedge B \rightarrow (A \Leftrightarrow B)$
• By constructing a truth table, we can determine whether the implication is valid.

Since all of the rows of the implication column of the truth table is true, the implication is valid, and thus the original entailment is correct.

Exercise 5.2b

• We can convert the entailment $(A\Leftrightarrow B)\models(A\wedge B)$ to an implication of the form $(A\Leftrightarrow B)\rightarrow(A\vee B)$
• By constructing a truth table, we can determine whether the implication is valid.

Since not every row of the implication column is true, the implication is not valid, and thus the original entailment is not correct.

Resolution Refutation

Resolution refutation is a technique for simplifying local propositions. There are three steps to perform resolution refutation:

1. Convert all sentences to Conjugative Normal Form (CNF)
2. Negate the desired conclusion
3. Apply the resolution rule, until we either:
   1. Derive false (a contradiction)
   2. Can't apply the rule anymore.

The resolution refutation rule is sound and complete (for propositional logic):

• If we derive a contradiction, the conclusion follows from the axioms (proof by contradiction)
• If we can't apply the rule any more, the conclusion cannot be proven from the axioms (no entailment, invalid statement).

Exercise 5.3

Use the resolution refutation rule to show

$$(P\wedge\neg P)\models R$$

(Note: negation can be represented by "$\neg$" or "~" or "!" or just plain "not")

Use the resolution refutation rule to show that $(P\wedge\neg P)\models R$. Resolution refutation is like a proof by contradiction. Assume that the statement that we want to prove is false, and then derive a contradiction (show that the knowledge base cannot be true, for the negated statement we want to prove).

Recall that the resolution refutation rule is given as follows:

1. The first step of resolution refutation is to convert all sentences in our axioms to Conjugative Normal Form. In this case, we only have a single sentence, which is straightforward to convert.
   $$(P\wedge\neg P)=(F\vee P)\wedge(\neg P \vee F)$$
2. Secondly, we negate the conclusion to get
   $$\neg (R) \equiv \neg R$$
3. We then apply the resolution refutation rule. Our first and second clauses are $F\vee P$ and $\neg P \vee F$ with conclusion $\neg R$.

4. Applying the resolution refutation rule yields $F \vee F = F$. We have derived $\text{False}$ which is a contradiction. Since $\text{False}$ entails anything including $R$ in this case, it is valid.

UQPark is a theme park with 5 rides. Bumper cars, carousel, haunted class, roller coaster and ferris wheel, where each ride can be turned off and on independently of other rides. After performing a cost-benefit analysis, UQPark Management decided that only 3 rides should be open on any given day, and that the set of rides that are open/closed must satisfy the following constraints:

1. Either bumper cars or carousel must be open
2. If bumper cars is closed, then roller coaster must be open.
3. If carousel is open, the either bumper cars or haunted class must be open too
4. If haunted class is open, then ferris wheel must be open too.
5. Bumper cars and ferris wheel cannot both be open at the same day.
6. If roller coaster is open, then ferris wheel must be open too.
7. If roller coaster is closed, then either haunted class or ferris wheel must be open.

UQ Park facilities thinks there is no combination of rides that can satisfy all of Management's constraints.

1. Please frame this problem as a satisfiability problem with propositional logic representation
2. Please solve the problem in (a) using DPLL. If both Management and Facilities are correct or both are incorrect, please also explain why using DPLL.

Tip: Assign W=Ferris Wheel.

Exercise 5.4a

1. Either bumper cars or carousel must be open
   $$B \vee C$$
2. If bumper cars is closed, then roller coaster must be open
   $$\neg B \rightarrow R \Rightarrow \neg (\neg B)\vee R\Rightarrow B \vee R$$
3. If carousel is open, then either bumper cars or haunted class must be open
   $$C\rightarrow (B \vee H) \Rightarrow \neg C \vee B \vee H$$
4. If haunted class is open, then ferris wheel must be open too
   $$H\rightarrow W \Rightarrow \neg H \vee W$$
5. Bumper cars and ferris wheel cannot both be open on the same day
   $$\neg(B\wedge W)\Rightarrow\neg B \vee \neg W$$
6. If roller coaster is open, then ferris wheel must be open too
   $$R \rightarrow W \Rightarrow \neg R \vee W$$
7. If roller coaster is closed, then either haunted class or ferris wheel must be open
   $$\neg R \rightarrow (H \vee W) \Rightarrow \neg(\neg R)\vee(H\vee W)\Rightarrow R\vee H\vee W$$

Exercise 5.4b

We count the occurrences of each variable in the CNF statement

Since B is the variable with the most entries (and will lead to the most simple answer) we choose to assign it first. We choose to assign B=True

This doesn't lead to a case where the statement is false, so we proceed with the assignment. We once again count the occurrences of each variable in our statement.

Since $W$ is the variable with the next-most entries we choose to assign it next. We first choose to assign W=True.

Since this assignment doesn't hold (statement isn't true for all assignment), we try W=False.

Counting the variable occurrences, we get H=2 and R=2. We choose to assign H=True

Since this variable assignment doesn't hold, we try to assign H=False.

Since this variable assignment doesn’t hold, and we have tried setting it to both true and false, we backtrack to the assignment of W. However, we have already tried all possibilities of assigning to W so we backtrack to the assignment of B. We try B=False.

Counting the variable occurrences gives us C=2, H=3, R=3, W=3. Since H is the variable with the next-most occurrences we choose to assign H=True.

Counting of variable occurrences gives us C=1, W=2, R=2. We choose to set W=True

We then set C=True

We set R=True