1. Converting a set of sentences to clausal form

7.20 Convert the following set of sentences to clausal form.
S1: $A \Leftrightarrow(B \vee E)$
S2: $E \Rightarrow D$
S3: $C \wedge F \Rightarrow \neg B$
S4: $E \Rightarrow B$
S5: $B \Rightarrow F$
S6: $B \Rightarrow C$
Give a trace of the execution of DPLL on the conjunction of these clauses (Russell & Norvig, 2010).

As for the "give a trace of the execution of DPLL on the conjunction of these clauses" part of this exercise, you can't execute pseudocode, which is all the textbook provides. So my trace was generated by modifying the official Python implementation provided by the textbook authors so that it outputs a trace. The function I call is dpll_satisfiable, which corresponds to Figure 7.17 in the textbook. I could have called dpll but dpll_satisfiable itself calls dpll, so this covers it all. Here is the input to the call in the lines starting with >>> and output from the trace follows in the lines not starting with >>>.

>>> S1 = '( A <=> (B | E) )'
>>> S2 = '( E ==> D )'
>>> S3 = '( C & F ==> ~B )'
>>> S4 = '( E ==> B )'
>>> S5 = '( B ==> F )'
>>> S6 = '( B ==> C )'
>>> s = expr(' & '.join([S1, S2, S3, S4, S5, S6]))
>>> dpll_satisfiable( s )
  Convering to_cnf...
    Convering to_cnf complete. Result:
  	(~B | A) & (~E | A) & (B | E | ~A) & (D | ~E) & 
    (~B | ~C | ~F) & (B | ~E) & (F | ~B) & (C | ~B)
  calling dpll() for the first time: 
  dpll() called...
    for c in clauses:
      (~B | A) is not False in model
      (~E | A) is not False in model
      (B | E | ~A) is not False in model
      (D | ~E) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = D  value = True
      calling dpll recursively
  dpll() called...
    for c in clauses:
      (~B | A) is not False in model
      (~E | A) is not False in model
      (B | E | ~A) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = None  value = None
      calling branching_heuristic
        result: P = A  value = True
      calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = None  value = None
      calling branching_heuristic
        result: P = C  value = True
      calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = None  value = None
      calling branching_heuristic
        result: P = F  value = True
      calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = B  value = False
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = E  value = True
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | ~E) is False in model!
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = B  value = False
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = E  value = True
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | ~E) is False in model!
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = F  value = True
      calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = B  value = False
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | E | ~A) is not False in model
      (B | ~E) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = None  value = None
      calling find_unit_clause
        result: P = E  value = True
      P is non-null: calling dpll from dpl
  dpll() called...
    for c in clauses:
      (B | ~E) is False in model!
  dpll() called...
    for c in clauses:
      (~B | A) is not False in model
      (~E | A) is not False in model
      (~B | ~C | ~F) is not False in model
      (B | ~E) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = E  value = False
      calling dpll from dpl
  dpll() called...
    for c in clauses:
      (~B | A) is not False in model
      (~B | ~C | ~F) is not False in model
      (F | ~B) is not False in model
      (C | ~B) is not False in model
      P is non-null: calling find_pure_symbol
        result: P = B  value = False
      calling dpll from dpl
  dpll() called...
    for c in clauses:
{D: True, A: False, E: False, B: False}

You can observe that the result of conversion by to_cnf was the following.

(~B | A) & (~E | A) & (B | E | ~A) & (D | ~E) & (~B | ~C | ~F) & (B | ~E) & (F | ~B) & (C | ~B),

This is the same as my result for conversion to CNF, only rearranged: $(\neg A \vee B \vee E) \wedge(\neg B \vee A) \wedge(\neg E \vee A) \wedge(\neg E \vee D) \wedge (\neg C \vee \neg F \vee \neg B)\wedge(\neg E \vee B)\wedge(\neg B \vee F)\wedge(\neg B \vee C)$

As for the final result from the trace, the output {D: True, A: False, E: False, B: False} indicates it was found to be satisfiable with these boolean values. More specifically, it means that if we take the CNF (or the original form) and substitute these boolean values (shown in green below so as not to confuse $\color{green}{\textbf{F}}\text{alse}$ with the variable $F$) we will get the following expression, which evaluates to True no matter what the values of $C$ and $F$ are.

$(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}}) \wedge(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}}) \wedge(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}}) \wedge(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{T}}) \wedge (\neg C \vee \neg F \vee \neg \color{green}{\textbf{F}})\wedge(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}})\wedge(\neg \color{green}{\textbf{F}} \vee \color{green}{\textbf{F}})\wedge(\neg \color{green}{\textbf{F}} \vee C)$,

This makes sense because all parenthesized portions contain $\neg \color{green}{\textbf{F}}$, which is True, and any disjunction involving True is True. The conjunction of all the parenthesized portions is also True, because a conjunction containing only True is True.

2. Expressing English Sentences in First-Order Logic

8.19 Assuming predicates $Parent(p, q)$ and $Female(p)$ and constants $Joan$ and $Kevin$, with the obvious meanings, express each of the following sentences in first-order logic. (You may use the abbreviation $\exists^{1}$ to mean "there exists exactly one.") (Russell & Norvig, 2010)

• "a. Joan has a daughter (possibly more than one, and possibly sons as well)."
  • $\exists\ c\ \ Parent(Joan,\ c) \wedge Female(c)$
• "b. Joan has exactly one daughter (but may have sons as well)."
  • $\exists^{1}\ c\ \ Parent(Joan,\ c) \wedge Female(c)$
• "c. Joan has exactly one child, a daughter."
  • $\exists\ c\ \ Parent(Joan,\ c) \wedge Female(c) \wedge(\forall\ x\ \ Parent(Joan,\ x) \Rightarrow x=c)$
• "d. Joan and Kevin have exactly one child together."
  • $\exists^{1}\ c\ \ Parent(Joan,\ c) \wedge Parent(Kevin,\ c)$
• "e. Joan has at least one child with Kevin, and no children with anyone else."
  • $\exists\ c_1\ \ Parent (Joan,\ c_1) \wedge Parent(Kevin,\ c_1) \wedge \forall\ c_2, p\ \ \left(Parent(Joan,\ c_2) \wedge Parent(p,\ c_2)\right) \Rightarrow\left(p= Joan \vee p= Kevin\right)$

3. Alan Perlis and the AI Endeavor

26.5 Alan Perlis (1982) wrote, “A year spent in artificial intelligence is enough to make one believe in God”. He also wrote, in a letter to Philip Davis, that one of the central dreams of computer science is that “through the performance of computers and their programs we will remove all doubt that there is only a chemical distinction between the living and nonliving world.” To what extent does the progress made so far in artificial intelligence shed light on these issues? Suppose that at some future date, the AI endeavor has been completely successful; that is, we have build intelligent agents capable of carrying out any human cognitive task at human levels of ability. To what extent would that shed light on these issues (Russell & Norvig, 2010)?

Although we don't have strong AI and thus the many of the characteristics of the human mind such as consciousness have not been produced in computers, our weak AI has made some headway in the area reproducing some cognitive tasks normally performed by humans. When our AI succeeds with this, it often does so with dazzling speed; much faster than humans. But there are still far more cognitive tasks we as humans can do that AI has, thus far, been unable to do. The quotes from Alan Perlis sound a bit overexcited in retrospect, but I think it's important to realize that it wasn't long ago where anything close to human-like cognition in a non-living machine such as an electronic computer was unthinkable. What happened during his lifetime must have been astounding, shattering a lot of beliefs humans had about themselves. So perhaps that's an explanation for his overly dramatic quotes. But as time progressed, the sense of marvel wears off and the distinction between computers and humans remain very pronounced and the notion that computers are capable of doing anything a human can do remains murky.

The question also asked what it will mean when "the AI endeavor has been completely successful." That depends on how you define the "the AI endeavor." If the endeavor is to make AI that is exactly like a humans, inside and out, then obviously a complete success would mean it would "remove all doubt that there is only a chemical distinction between the living and nonliving world." If the endeavor is to make them act rationally and be more useful to humans in performing more cognitive tasks but not quite all the tasks a human can perform, then the distinction would obviously remain.

4. Societal Threats of AI

26.8 Analyze the potential threats from AI technology to society. What threats are most serious, and how might they be combated? How do they compare to the potential benefits (Russell & Norvig, 2010)?

Future potential threats if strong AI ever comes to fruition could go as far as your imagination will allow, so I'll leave it at that. But current potential threats are a bit more limited since we only have weak AI. Any technology that doesn't have a will of its own, such as weak AI and not strong AI, is, for the most part, doing our bidding. So the threat from this weak AI is essentially an embodiment of our threat to ourselves, whether intentional or not. Although AI is powerful, the threat is not fundamentally different from the threat we pose to ourselves with other forms of technology.

• Beside intentionally nefarious uses of AI, things can go wrong by flaws in AI systems relied upon for important public or personal services. This can be combatted with stricter engineering practices in development of AI in conjunction with careful consideration before relying the resulting AI for critical uses.
• Even the AI itself doesn't "go wrong," the use of AI can essentially atrophy our own human abilities as we rely on AI to do what we would normally do ourselves. The remedy for this is behavioral, via awareness of its effect on us.
• AI will certainly replace jobs but, like most new technologies in the past did, it will likely create new jobs as well. With AI doing more for us, this could free us up to work on higher goals, which could stimulate the creation of new products or new fields of work, both of which can results in the formation of new jobs. Or we could squander the opportunity and fall into economic depression. It's all in how we use it. If we think of AI it as an extension of our human abilities rather than a replacement of them, AI can enhance our power as humans rather than take away from it.

References

• Russell, S., & Norvig, P. (2010). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson Prentice Hall.