In this assignment, you will get some hands-on experience with logic. You'll see how logic can be used to represent the meaning of natural language sentences, and how it can be used to solve puzzles and prove theorems. Most of this assignment will be translating English into logical formulas, but in Problem 4, we will delve into the mechanics of logical inference. Finally, for the ethics question you will revisit the ethical frameworks and concepts you learned about this quarter through once again writing negative impact statements.

NOTE: There are mandatory written questions after the extra credit problem 5 - Problem 6 and 7. Do not forget to answer these questions! Also for this assignment only, there are no hidden test cases for the programming questions -- if you pass all the visible test cases, then you will get full credit!

We've created a LaTeX template here for you to use that contains the prompts for each question.

To get started, launch a Python shell and try typing the following commands to add logical expressions into the knowledge base.

from logic import *
Rain = Atom('Rain')           # Shortcut
Wet = Atom('Wet')             # Shortcut
kb = createResolutionKB()     # Create the knowledge base
kb.ask(Wet)                   # Prints "I don't know."
kb.ask(Not(Wet))              # Prints "I don't know."
kb.tell(Implies(Rain, Wet))   # Prints "I learned something."
kb.ask(Wet)                   # Prints "I don't know."
kb.tell(Rain)                 # Prints "I learned something."
kb.tell(Wet)                  # Prints "I already knew that."
kb.ask(Wet)                   # Prints "Yes."
kb.ask(Not(Wet))              # Prints "No."
kb.tell(Not(Wet))             # Prints "I don't buy that."

==== Knowledge base [3 derivations] ===
* Or(Not(Rain),Wet)
* Rain
- Wet

The operations And and Or only take two arguments. If we want to take a conjunction or disjunction of more than two, use AndList and OrList. For example: AndList([Atom('A'), Atom('B'), Atom('C')]) is equivalent to And(And(Atom('A'), Atom('B')), Atom('C')).

Problem 1: Propositional logic

Write a propositional logic formula for each of the following English sentences in the given function in submission.py. For example, if the sentence is "If it is raining, it is wet," then you would write Implies(Atom('Rain'), Atom('Wet')), which would be $\text{Rain} \to \text{Wet}$ in symbols (see examples.py). Note: Don't forget to return the constructed formula!

1. "If it's summer and we're in California, then it doesn't rain."
2. "It's wet if and only if it is raining or the sprinklers are on."
3. "Either it's day or night (but not both)."

    python grader.py 1a
    

    Your formula (And(Rain,Wet)) says the following model is FALSE, but it should be TRUE:
    * Rain = False
    * Wet = True
    * (other atoms if any) = False
    

In this model, it's not raining and it is wet, which satisfies the correct formula $\text{Rain} \to \text{Wet}$ (TRUE), but does not satisfy the incorrect formula $\text{Rain} \wedge \text{Wet}$ (FALSE). Use these counterexamples to guide you in the rest of the assignment.

Problem 2: First-order logic

Write a first-order logic formula for each of the following English sentences in the given function in submission.py. For example, if the sentence is "There is a light that shines," then you would write Exists('$x', And(Atom('Light', '$x'), Atom('Shines', '$x'))), which would be $\exists x . \text{Light}(x) \wedge \text{Shines}(x)$ in symbols (see examples.py).

Tips:

• You can directly write '$x' instead of Variable('$x') to represent a variable symbol.
• Python tuples can span multiple lines, which help with readability when you are writing logic expressions (some of them in this homework can get quite large).

1. "Every person has a parent."

Note: You do NOT have to enforce that the parent is a "person".

2. "At least one person has no children."

Note: You do NOT have to enforce that the child is a "person".

3. Create a formula which defines Father(x,y) in terms of Male(x) and Parent(x,y).
4. Create a formula which defines Granddaughter(x,y) in terms of Female(x) and Child(x,y).

Note: It is ok for a person to be their own child.

Problem 3: Liar puzzle

1. Mark says: "It wasn't me!"
2. John says: "It was Nicole!"
3. Nicole says: "No, it was Susan!"
4. Susan says: "Nicole's a liar."
5. You know that exactly one person is telling the truth.
6. You also know exactly one person crashed the server.

1. Fill out liar() to return a list of 6 formulas, one for each of the above facts.
   The grader is set up such that you could run individual parts 3a-0 to 3a-5 to debug each formula only if you implement them in the order specified.

    python grader.py 3a-0
    python grader.py 3a-1
    python grader.py 3a-2
    python grader.py 3a-3
    python grader.py 3a-4
    python grader.py 3a-5
    python grader.py 3a-all  # Tests the conjunction of all the formulas
    

    python grader.py 3a-run
    

Problem 4: Odd and even integers

In this problem, we will see how to use logic to automatically prove mathematical theorems. We will focus on encoding the theorem and leave the proving part to the logical inference algorithm. Here is the theorem:

1. Each number $x$ has exactly one successor, which is not equal to $x$.
2. Each number is either odd or even, but not both.
3. The successor of an even number is odd.
4. The successor of an odd number is even.
5. For every number $x$, the successor of $x$ is larger than $x$.
6. Larger is a transitive property: if $x$ is larger than $y$ and $y$ is larger than $z$, then $x$ is larger than $z$.

• For each number, there is an even number larger than it.

Note: in this problem, "larger than" is just an arbitrary relation, and you should not assume it has any prior meaning. In other words, don't assume things like "a number can't be larger than itself" unless explicitly stated.

1. Fill out ints() to construct 6 formulas for each of the constraints. The consequence has been filled out for you (query in the code).
   The grader is set up such that you could run individual parts 4a-0 to 4a-5 to debug each formula only if you implement them in the order specified. You can test your code using the following commands:

       python grader.py 4a-0
       python grader.py 4a-1
       python grader.py 4a-2
       python grader.py 4a-3
       python grader.py 4a-4
       python grader.py 4a-5
       python grader.py 4a-all  # Tests the conjunction of all the formulas
       

   To finally prove the theorem, tell the formulas to the knowledge base and ask the query by running model checking (on a finite model):

       python grader.py 4a-run
       

Problem 5: Semantic parsing (extra credit)

Semantic parsing is the task of converting natural lanugage utterances into first-order logic formulas. We have created a small set of grammar rules in the code for you in createBaseEnglishGrammar(). In this problem, you will add additional grammar rules to handle a wider variety of sentences. Specifically, create a GrammarRule for each of the following sentence structures.

1. Example: Every person likes some cat. General template:

   $Clause ← every $Noun $Verb some $Noun

2. Example: There is some cat that every person likes. General template:

   $Clause ← there is some $Noun that every $Noun $Verb

3. Example: If a person likes a cat then the former feeds the latter. General template:

   $Clause ← if a $Noun $Verb a $Noun then the former $Verb the latter

    $ python nli.py
    
    > Every person likes some cat.
    
    >>>>> I learned something.
    ------------------------------
    > Every cat is a mammal.
    
    >>>>> I learned something.
    ------------------------------
    > Every person likes some mammal?
    
    >>>>> Yes.
    

Problem 6: Explainability of Logic-Based Systems

The notion that AI systems should be explainable and their decisions interpretable has gained traction. For instance, GDPR’s Article 15 requires that individuals be provided “meaningful information” about the logic of automated decisions. Independently of legal considerations, explainable AI protects the interests of both end users (the people employing AI to make or inform decisions) and to stakeholders (individuals affected by automated decisions). These are some of the considerations cited in the literature:

1. Respect: when decisions that affect you are made intelligible to you, this is considered an expression of respect for your status as a human being whose interests are worthy of consideration.
2. Assessing fairness of rules: knowing what rules are applied to reach a decision, we have the ability to evaluate whether the rules are fair and whether they are fairly applied to us.
3. Contesting and correcting decisions: understanding a decision we disagree with, allows us to contest it.
4. Ability to change user behavior: understanding a decision that has a negative impact on us allows us to adapt our behavior in order to obtain different results in the future.

Explanability has many different meanings (see this paper by Andrew Selbst and Solon Barocas; and this paper by Finale Doshi Velez and Been Kim). Intuitively, logic-based systems should have more explanability power than machine learning-based “black-box” systems. In this problem, let us explore what kind of explanability logic-based systems might provide and which human interests are protected.

Consider the Liar’s Puzzle from Problem 3. Here, the first-order logic system takes in a set of facts and reasons over them to produce a conclusion. In this case, the conclusion judges the truthfulness of each person, which could carry with it real-world consequences. For example, someone might be fired if they are found guilty of crashing the server, whether they did it or not (AI is used widely for the allocation of healthcare resources, credit scoring, insurance, and content moderation, among other consequential domains).

1. Besides returning the final answer, what does a first-order logic system return that could be considered an explanation?
   1-2 sentences answering the question.
2. Why might this explanation not be adequate?

   Hint: think about model misspecification or framing of the question posed to the logic-based system.

   1-2 sentences answering the question.
3. (extra credit) Now, reflect on the four explainability considerations defined in this problem. Are any of these met by the explanations produced by a logic-based system?
   2-4 sentences answering the question.

Problem 7: Ethics and Explainability through Datasets for “Black-Box” Systems

Recall that in Problem 4 of Homework 2 on Sentiment Analysis, we briefly explored the spurious correlation problem through two classifiers for detecting toxicity in online comments: one based on the presence of demographic mentions (Classifier D) and one based on the presence of toxic words (Classifier T). In this problem, we will revisit the spurious correlation problem and explore the potential ethical issues of large datasets both inside and outside of the context of explainable artificial intelligence.

1. Large language models (LLMs), like OpenAI’s ChatGPT and Google’s Bard, are trained on massive amounts of data scraped from various parts of the Internet, like Wikipedia and Reddit. Recent work has shown that LLMs and large vision models are susceptible to harmful biases, like gender-based stereotyping [1], in part derived from spurious correlations, but also due to the biases embedded in society. For example, in April 2023, Hadas Kotek discovered explicit gender bias in ChatGPT that insistently genders “doctor” as male and “nurse” as female. [2]

   Scholars have aimed to examine the contents and sources of these LLMs’ training data more closely, and they have found that said data contains a non-trivial amount of biased, harmful, or otherwise “undesirable” content, such as hate speech. [3] Models are biased because the data used to train them are biased. Thus, by understanding the data used to train these LLMs, we begin to see why such biases exist (and persist) in the models and any downstream tasks that use these models.

   Here is a quick video about Bias and Fairness in AI [link] [4], as well as the related articled in [5].

   In the video and article linked above, there are several forms of bias that can contribute to a biased AI model. In particular, three key types of data bias are: historical bias, representation bias, and measurement bias. Which form(s) of data bias do you think is the main contributing factor to the gender bias discussed above, and why?

   What form(s) of bias are contributing, and 1-2 sentences explaining why.
2. (extra credit) Spend some time with the articles and resources linked in the footnotes. What are some other forms of bias that foundation models could exhibit due to dataset bias? [If you have a ChatGPT account, see if you can replicate Kotek’s findings.]
   2-4 sentences answering the question.
3. AI art has been a controversial topic since AI image generators became mainstream. Stability AI, the organization behind the powerful image generator Stable Diffusion, is facing multiple lawsuits from artists [6] and other groups (such as Getty Images [7]) for using artwork and photos in training without permission. Factors like copyright law and privacy all come into play.

   In contrast, researchers with Meta AI “licensed assets from Getty Images [and] worked with trained third-party annotators to create new [images] similar to existing ones that had been shared on social media sites” [8]

   Imagine that you as a researcher are building an image dataset for a generative model. What is one measure you could take to ensure that your dataset collection is ethical and legal? [9]

   1-2 sentences describing one thing you would do. Drawing from online sources (either linked in the footnotes or through your own searches) is highly encouraged.
4. (extra credit) Researchers have begun using advanced generative AI like ChatGPT to assist in dataset creation. One advantage of doing so is that it is much easier to create large amounts of custom data, which makes dataset creation much more affordable. One drawback of doing so is that ChatGPT can be wrong, which can introduce artifacts and lower-quality data into models trained on the ChatGPT-assisted datasets. Do you think the advantages outweigh the drawbacks, or do the potential consequences outweigh the potential benefits? Can you think of other pros and cons?
   Whether you think the advantages outweigh the disadvantages, or the other way around, and 1-2 sentences explaining why. At least one additional pro or con of using generative AI for dataset creation.

[1] For more about biases learned by large models (both text-based and image-based), check out the work of Davor Petreski, Ibrahim C. Hashim, (https://link.springer.com/article/10.1007/s00146-022-01443-w), Robert Wolfe, and Aylin Caliskan (https://faculty.washington.edu/aylin/index.html).

[2] https://hkotek.com/blog/gender-bias-in-chatgpt/

[3] What's in the Box? A Preliminary Analysis of Undesirable Content in the Common Crawl Corpus https://arxiv.org/abs/2105.02732

[4] See https://www.youtube.com/watch? v=fA5xpRnqbKM&ab_channel=FiddlerAI

[5] https://towardsdatascience.com/understanding-bias-and-fairness-in-ai- systems-6f7fbfe267f3

[6] Artists Are Suing Artificial Intelligence Companies and the Lawsuit Could Upend Legal Precedents Around Art https://www.artnews.com/art-in-america/features/midjourney-ai-art- image-generators-lawsuit-1234665579/

[7] Getty Images Sues Stability AI Over Photos Used to Train Stable Diffusion Image Generator [link]

[8] https://ai.facebook.com/blog/hateful-memes-challenge-and-data-set/

[9] https://research.aimultiple.com/data-collection-ethics/