English to Propositional Logic

Propositions: The Atoms of Logic

The fundamental unit of propositional logic is the proposition. A proposition is simply a declarative statement that has a definite truth value: it is either true or false. It cannot be both, and it cannot be neither.

Consider these examples:

• "The sky is blue." (A true proposition)
• "2 + 2 = 5." (A false proposition)
• "There is life on Mars." (A proposition whose truth value is unknown, but it is either true or false)

Conversely, questions, commands, or gibberish are not propositions because they don't have a truth value:

• "Where are you?" (A question)
• "Get me a drink." (A command)
• "Akjsdf!" (Gibberish)

Since you've worked with boolean types in programming, you can think of a proposition as being analogous to a boolean variable. It can hold one of two values: True or False.

To work with these statements mathematically, we represent simple propositions (called atomic propositions) with variables, typically capital letters like P, Q, and R.

For instance:

• P: "It is raining."
• Q: "The server is online."

The following resource provides a clear definition of a proposition and gives further examples of what is, and what is not, a proposition.

Logical Connectives: Building Compound Statements

Simple propositions aren't very expressive on their own. We create complex, compound propositions by joining simple ones together using logical connectives. These are the logical equivalents of operators like && (AND), || (OR), and ! (NOT) that you're familiar with from programming.

There are five primary connectives we will use. Different texts sometimes use different symbols, but the ones below are the most common in modern computer science and mathematics.

This table summarizes these connectives, which you can see visualized in the "Propositional logic" chart. Note that the symbols in the chart for implies (→) and if and only if (↔) are slightly different from our standard notation, but represent the same concepts.

Let's explore each of these in more detail. The following resource provides an excellent, in-depth look at each connective and the many ways they can appear in English.

Here's a summary of key points and tricky phrases to watch out for:

• Negation ($\neg$): Always define your proposition in the affirmative. If the sentence is "The system is not online," define P as "The system is online," and then write the full expression as $\neg P$.
• Conjunction ($\wedge$): This isn't just "and." Words like "but," "although," "moreover," and "while" all function as logical conjunctions. They assert that both connected statements are true.
• Disjunction ($\vee$): This is an inclusive OR, meaning "one, or the other, or both." The word "unless" is a tricky but common way to express disjunction. The statement "I will go to the park unless it rains" translates to "I will go to the park OR it rains" ($P\vee R$).
• Conditional ($\to$): This represents an "if-then" relationship. The "if" part is the antecedent, and the "then" part is the consequent. The order in English can be confusing.
  • "If P, then Q" translates to $P\to Q$.
  • "Q if P" also translates to $P\to Q$. The clause immediately following "if" is the antecedent.
  • "P only if Q" translates to $P\to Q$. Think of it as "If P is true, then Q must also be true."
• Biconditional ($\leftrightarrow$): This signifies that two propositions have the same truth value. It's a two-way street. The most common phrasing is "if and only if" (often abbreviated "iff"), but also look for "is a necessary and sufficient condition for."

The Art of Translation

Now, let's combine these ideas to translate full sentences. The process involves identifying the atomic propositions, spotting the connectives, and preserving the logical structure with parentheses.

Your experience with order of operations in both arithmetic and programming is directly applicable here. Parentheses are used to resolve ambiguity, ensuring there is only one way to interpret a compound proposition.

For a great walkthrough of the translation process, this video provides several clear, step-by-step examples.

A Step-by-Step Example

Let's translate a complex sentence together.

Sentence: "If the API is responsive and the cache is warm, then the dashboard will load; otherwise, the dashboard will not load and an alert will be sent."

1. Identify and label the atomic propositions:

   • P: The API is responsive.
   • Q: The cache is warm.
   • R: The dashboard will load.
   • S: An alert will be sent.

2. Break down the sentence into logical parts:

   • The core structure is separated by the semicolon and the word "otherwise." "Otherwise" implies "if not the first condition, then the second." This suggests a larger conditional structure.
   • Part 1: "the API is responsive and the cache is warm" $\to (P\wedge Q)$.
   • Part 2: "the dashboard will load" $\to R$.
   • So the first clause is: "If (Part 1), then (Part 2)" $\to (P\wedge Q)\to R$.

3. Analyze the "otherwise" part:

   • The "otherwise" refers to the failure of the initial "if" condition. So, "if it's not the case that (the API is responsive and the cache is warm)...". This is $\neg (P\wedge Q)$.
   • What happens in this case? "the dashboard will not load and an alert will be sent."
   • This translates to: $\neg R\wedge S$.
   • So the second major clause is: "If $\neg (P\wedge Q)$, then $(\neg R\wedge S)$". This is $\neg (P\wedge Q)\to (\neg R\wedge S)$.

4. Combine the main clauses:

   • The full sentence asserts that both of these conditions hold. The first clause covers the "success" case, and the "otherwise" clause covers the "failure" case. We connect them with an "and".

Final Translation:

This may seem complex, but by breaking it down systematically, we can translate even very intricate sentences into a precise logical form. The "Translation Tips" resource below offers more excellent strategies for this process.

Conclusion

In this lesson, we have laid the foundation for our study of logic. You've learned how to transform natural language into the structured and precise format of propositional logic.

Here are the key takeaways:

• A proposition is a declarative statement that is either true or false. We represent them with variables (e.g., P, Q).
• We combine simple propositions into compound ones using five logical connectives: negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), conditional ($\to$), and biconditional ($\leftrightarrow$).
• Translating from English requires careful identification of atomic propositions and the keywords that signify connectives.
• Parentheses are crucial for grouping and removing ambiguity, much like in arithmetic or programming expressions.

In our next lesson, we will move from syntax to semantics. You will learn how to evaluate the truth of these compound propositions for all possible scenarios using truth tables. This will allow us to determine logical equivalence and analyze the validity of arguments.