Translating Integer and Algorithm Statements into Propositions

What is a Proposition?

Before we can analyze complex statements, we need to agree on what constitutes a basic, unambiguous logical statement. In mathematics, this is called a proposition. A proposition is simply a declarative sentence that is definitively either true or false, but not both.

For a clear explanation of what makes a statement a proposition, please watch the first part of the following video. It provides several examples of what is, and what is not, a proposition.

As you saw, a statement like "The number 13 is prime" is a proposition (it's true), and "2 + 2 = 5" is also a proposition (it's false). However, a command like "Run the program" or a question "Is the network secure?" are not propositions.

Combining Propositions: The Logical Connectives

Propositions become truly powerful when we combine them. We do this using a set of operators called logical connectives. You already use these intuitively in both natural language and programming (and, or, not). Here, we will define them formally.

The following reading from the MIT OpenCourseWare notes for "Mathematics for Computer Science" introduces the five fundamental connectives. As you read, pay close attention to the truth tables, which are the formal definitions of how each connective works.

To summarize, here are the five connectives and their common symbols. Different contexts (mathematics, programming, circuit design) use different notation, so it's good to be familiar with them.

The IMPLIES connective (P → Q) is often the trickiest. Think of it as a promise. The statement "If it is raining, then I will carry an umbrella" is only broken (false) if it is raining (P is true) and I don't carry an umbrella (Q is false). In all other scenarios, the promise holds.

From English to Logic: The Art of Translation

Now we can apply these tools to translate natural language statements into formal logic. This process forces clarity and removes ambiguity. The learning outcome for this lesson specifically mentions statements about integers and algorithms, which are central to computer science.

The general process is:

1. Identify the basic atomic propositions — the simple declarative sentences.
2. Assign a variable (like P, Q, R) to each atomic proposition. It's good practice to define them in their positive form (e.g., "The system is secure" rather than "The system is not secure").
3. Identify the connectives (not, and, or, if-then, etc.).
4. Write the final expression using the variables and connective symbols.

This next video provides a step-by-step walkthrough of this translation process with several well-chosen examples. Pay special attention to the segment that distinguishes "if" from "only if," as this is a very common point of confusion.

Let's work through an example relevant to your interest in cybersecurity.

Statement: "If a login attempt fails and the account is not locked, then a security alert is logged."

1. Atomic Propositions:

   • P: A login attempt succeeds.
   • Q: The account is locked.
   • R: A security alert is logged.

2. Translate Phrases:

   • "a login attempt fails" is ¬P (the negation of "a login attempt succeeds").
   • "the account is not locked" is ¬Q.
   • "a security alert is logged" is R.

3. Combine with Connectives: The structure is "If (A and B), then C".

   • The "if" part is (¬P ∧ ¬Q).
   • The "then" part is R.

4. Final Expression: $(\neg P\wedge \neg Q)\to R$

Logic in Algorithms

This formal structure isn't just an abstract exercise; it's exactly what computers do. The conditional logic you write in Python with if, and, or, and not is a direct implementation of these principles. By translating code into propositional logic, you can analyze and even simplify it.

The next reading from the same MIT notes explores this connection directly.

The example in the text uses symbols from C/Java (&&, ||), but the concept is identical in Python. The expression A OR (.NOT.A/ AND B/) from the reading is equivalent to the Python code A or (not A and B). As the text shows, this whole expression is logically equivalent to simply A or B. Understanding this can help you write cleaner and more performant code.

As a final self-check, try translating these sentences. You can find many similar problems with answers in the Exercises section of the Runestone Academy text Propositions and Logical Operators (resource LINK), specifically Exercise 2.

1. An integer x is greater than 10 or it is not a positive number.
2. If an integer x is even, then x+1 is odd.
3. A user can access the file only if they are an administrator or they are the owner of the file.

Conclusion

In this lesson, you've taken the first step toward speaking the language of mathematics and computer science with precision. We have established a solid foundation by:

• Defining a proposition as a statement that is either true or false.
• Introducing the five logical connectives: NOT (¬), AND (∧), OR (∨), IMPLIES (→), and IFF (↔).
• Practicing the translation of statements about integers and algorithms into symbolic logic.

You've seen how these "abstract" concepts directly map to the conditional logic you use in programming. Mastering this translation skill is crucial for everything that follows, from proving an algorithm is correct to understanding the security guarantees of a cryptographic protocol.

In our next lesson, we will expand our logical toolkit by introducing quantifiers. These will allow us to handle statements involving "for all" ($\forall$) and "there exists" ($\exists$), enabling us to express much more complex and powerful ideas.