Ch 3. Logic and Proofs
3.1 Propositions
In logic, a proposition is a declarative statement that can be true or false, but not both. They express a complete thought and have a definite truth value. Examples of propositions are “the server is online”, “5 is greater than 3”, and “the database is empty.”
A statement that is a command, which does not have a true value, is not a proposition, such as “Close the window.” A statement that is a question is also not a declarative statement, such as “What time is it?”
In logic, we use variables, typically lowercase letters like [latex]p[/latex], [latex]q[/latex], [latex]r[/latex], etc., to represent propositions. This allows us to work with abstract logical structures without focusing on the specific content of each statement.
When we want to combine two propositions with the word “and”, we use the logical operation of conjunction, denoted [latex]p \land q[/latex]. This proposition is true only when both [latex]p[/latex] and [latex]q[/latex] are true.
A disjunction uses the word “or”, denoted by [latex]p \lor q[/latex], and is true when at least one of [latex]p[/latex] or [latex]q[/latex] is true.
Example 3.1
Let [latex]p[/latex]: "The server is online."
Let [latex]q[/latex]: "The database is accessible."
[latex]p \land q[/latex]: "The server is online, and the database is accessible."
[latex]p \lor q[/latex]: "The server is online or the database is accessible."
A truth table is a tool for listing all possible truth values of logical expressions based on the truth values of their components.
Truth Table for [latex]p \land q[/latex]:
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \land q[/latex] |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Example 3.2
If the server is online (T) and the database is not accessible (F), then [latex]p \land q[/latex] is false.
Programming Example 3.1 (Pseudocode)
IF server_is_online AND database_is_accessible THEN
DISPLAY "System is fully operational."
ELSE
DISPLAY "System is not fully operational."
Truth Table for [latex]p \lor q[/latex]:
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \lor q[/latex] |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Example 3.3
If either the server or the database is working, the system is partially operational.
Programming Example 3.2 (Pseudocode)
IF server_is_online OR database_is_accessible THEN
DISPLAY "System is partially operational."
ELSE
DISPLAY "System is offline."
Negation is the logical operation that reverses the truth value of a proposition. It is denoted by [latex]\neg p[/latex].
| [latex]p[/latex] | [latex]p \lor q[/latex] |
|---|---|
| T | F |
| F | T |
Example 3.4
Let [latex]p[/latex]: "The user is logged in."
Then [latex]\neg p[/latex]: "The user is not logged in"
Programming Example 3.3 (Pseudocode)
IF NOT user_is_logged_in THEN
DISPLAY "Please log in to continue."
Real-World Example 3.1: System Access Control
Consider a business application that grants access based on two conditions:
[latex]p[/latex]: The user is authenticated
[latex]q[/latex]: The user has admin privileges
Using logical operations:
[latex]p \land q[/latex]: The user is authenticated and has admin rights
[latex]\rightarrow[/latex] grant full access.
[latex]p \lor q[/latex]: The user is authenticated or has admin rights
[latex]\rightarrow[/latex] grant limited access.
[latex]\neg p[/latex]: The user is not authenticated
[latex]\rightarrow[/latex] deny access.
Programming Logic (Pseudocode)
IF user_is_authenticated AND user_is_admin THEN
DISPLAY "Full access granted."
ELSE IF user_is_authenticated OR user_is_admin THEN
DISPLAY "Limited access granted."
ELSE
DISPLAY "Access denied."
