Propositional Logic: Introduction and Key Concepts

Propositional Logic: Introduction

This section introduces propositional logic as the simplest form of logic and the central theme for reasoning in mathematics and computer science. The plan is to start with an introduction to how logic works and why it is useful, then to cover the basic connectives used to form complex statements, followed by propositional equivalences and eventually how to establish truth through proofs. Propositional logic deals with basic statements (or propositions) such as “x is smaller than five” or “there are four lights,” and how these can be combined using logical operators. A fundamental idea is that a proposition is either true (denoted by
T) or false (denoted by
F), while some statements depend on context and are thus contingent. In this course, the simplest form of combining propositions uses logical connectives such as NOT, AND, OR, XOR, IMPLICATION, and BICONDITIONAL. A basic proposition is often denoted by a simple letter such as p or q, for example, “x is smaller than five.” The next topic after this week’s introduction is predicate logic, which introduces variables and quantifiers. Logic is also applicable to programming, where conditions like whether a variable x is smaller than another or whether two values are unequal can be evaluated and combined with connectives to determine program state.

Validity of Arguments: Examples and Rules

To decide whether an argument is valid means that the conclusion must follow from the premises in all cases. The lecture provides several motivating examples. The first example uses two facts: A: “It is raining” and B: “If it is raining, then the grass is wet.” From A and B, we can conclude that the grass is wet. This is the rule known as modus ponens: if A and A
ightarrow B hold, then we may infer B. Formally, this can be written as the sequent
A,\, (A
ightarrow B) \vdash B.

A second example uses A: “the grass is wet” and B: “If it is raining, then the grass is wet.” From A and B, we cannot conclude that it is raining. The grass can be wet for reasons other than rain, so the argument is not valid. This illustrates that from Q (the grass is wet) and P
ightarrow Q, we cannot infer P in general.

A third example uses A: “the grass is not wet” (i.e.,
eg Q) and B: “If it is raining, then the grass is wet” (i.e., P
ightarrow Q). From P
ightarrow Q and
eg Q we can conclude
eg P by modus tollens: if the implication would hold but the consequent is false, then the antecedent cannot be true. This yields a valid argument (P
ightarrow Q),\,
eg Q \vdash
eg P.

A fourth example concerns a more general statement about syllogistic reasoning: A: “All lecture halls are uncomfortable.” B: “Auditorium 2 is a lecture hall.” From these premises, one can conclude that Auditorium 2 is uncomfortable. This is valid by universal reasoning, which will be discussed in more depth under universal quantification in the next week’s lecture. The main point is that these examples illustrate how truth values propagate through logical rules.

Propositional Connectives and Basic Propositions

Logic in propositional form relies on a small set of connectives to build complex statements. The core connectives discussed are NOT (¬), AND (∧), OR (∨), EXCLUSIVE OR (⊕), IMPLICATION (→), and BI-IMPLICATION (↔). Basic propositions are denoted by letters such as p, q, r, like the statement “x is smaller than five” or “there are four lights.” Using these connectives, we can build compound propositions such as:

• conjugation: p \,\land\, q (p and q)

• disjunction: p \,\lor\, q (p or q)

• negation: \neg p (not p)

• exclusive or: p \oplus q (p XOR q)

• implication: p \rightarrow q (if p then q)

• biconditional: p \leftrightarrow q (p if and only if q)

A typical example is the statement: p\rightarrow q expresses that if it is sunny (p), then I go for a run (q). Another example is: r \rightarrow \neg q, meaning if I go to the theater (r), then I do not go for a run (¬q). The connective NOT allows us to form negations such as \neg q. These constructions let us express a range of everyday reasoning with a precise logical form.

The notion of truth values is central: some propositions are always true (tautologies) or always false (contradictions), while others depend on context. For example, the proposition "a triangle has three sides" is always true, while "London is in Denmark" is always false. Other statements, like whether it is sunny or whether there are five lights, depend on the context. These distinctions help in understanding which propositions are contingent and which are logically valid in all interpretations.

Context-Dependent Propositions and Compound Forms

Compound propositions arise by combining simpler propositions with connectives. For example, the conjunction p \land q corresponds to "it is sunny and I go for a run" if p is "it is sunny" and q is "I go for a run." The implication p \rightarrow q corresponds to "if it is sunny, then I go for a run." The example "If I go to the theater, then I do not go for a run" uses the implication together with negation: r \rightarrow \neg q. These forms lay the groundwork for reasoning about what follows from assumed facts in a systematic way, rather than relying on intuition alone.

Proofs: Establishing Truth from Assumptions

Once we have a precise language for statements, we can establish their truth by reasoning from assumptions using proofs. In mathematics, we start from definitions of objects and axioms, then derive theorems and lemmas. The lecture provides a basic illustration: suppose we have three statements
1) P \rightarrow Q (if it is sunny, then I go for a run),
2) R \rightarrow \neg Q (if I go to the theater, then I do not go for a run),
3) R (I go to the theater).
From (2) and (3) we obtain \neg Q, and from (1) together with \neg Q we obtain \neg P by modus tollens. Thus the conclusion is that it is not sunny. This is a simple demonstration of how a proof can be used to deduce new truths from a given set of assumptions. The broader aim is to show how mathematics proceeds: definitions lead to structured deductions, which we often express as theorems or lemmas.

Next week’s coverage will extend propositional logic to predicate logic, where variables and quantifiers (such as universal ∀ and existential ∃) allow us to talk about statements that are true for all or some values of a variable. In the meantime, we see how logic provides a precise language for stating and testing the validity of arguments, and how it underpins both mathematical proof and reasoning about programs.