Propositional Logic

Propositional logic is the branch of logic that deals with propositions—statements that are either definitely True (T) or definitely False (F). It is the language that computers reflect in their hardware, where every signal is high (1) or low (0).

1. What is a Proposition?

A proposition must have a fixed truth value.

• Propositions:
  • “The sun is a star.” (True)
  • “2 + 2 = 5.” (False)
• Non-Propositions:
  • “Close the door!” (Command)
  • “What time is it?” (Question)
  • “This sentence is false.” (The Liar’s Paradox - it cannot be consistently True or False)

2. Logical Operators in Code

In programming, we use operators to combine these truth values. Let’s see how the basic connectives behave using Python’s boolean logic.

# Logical Truth Tables in Python
def truth_table():
  print("P      | Q      | P AND Q | P OR Q | NOT P")
  print("-" * 45)
  for P in [True, False]:
      for Q in [True, False]:
          res_and = P and Q
          res_or = P or Q
          res_not = not P
          print(f"{str(P):<6} | {str(Q):<6} | {str(res_and):<7} | {str(res_or):<6} | {str(res_not):<5}")

truth_table()

3. The Implication ($\implies$)

The implication “If $P$, then $Q$” is a promise. It is only broken (False) if $P$ is True but $Q$ fails to happen (is False).

Example: “If you pass the exam ($P$), I will buy you a car ($Q$).”

• If you pass ($P=T$) and you get the car ($Q=T$): Promise kept.
• If you pass ($P=T$) but you don’t get the car ($Q=F$): Promise broken.
• If you fail ($P=F$): It doesn’t matter if I buy you a car or not; the promise wasn’t triggered. Therefore, the statement is vacuously true.

4. De Morgan’s Laws in Action

De Morgan’s laws allow us to simplify complex logic. In code, this is vital for readability.

• not (A and B) is the same as (not A) or (not B)
• not (A or B) is the same as (not A) and (not B)

# Testing De Morgan's Law
A = True
B = False

# Left side: not (A and B)
lhs = not (A and B)
# Right side: (not A) or (not B)
rhs = (not A) or (not B)

print(f"not (A and B): {lhs}")
print(f"(not A) or (not B): {rhs}")
print(f"They are equal: {lhs == rhs}")

Exercises