Propositional Logic

Proposition Logic

• Humans have long strived to create a formal, mathematical description of the principles of human thought
• The goals are to identify correct arguments and what makes them valid based on their logical form
• The pursuit of these goals dates back to ancient times, with significant development by Aristotle (384-322 BC) and in the Middle Ages
• Rapid advancements occurred in the nineteenth and twentieth centuries, starting around 1930
• Formalized reasoning is crucial in formal logic and is applied to studying mathematical proofs
• Formal logic is used in computer science for database theory, AI, program language design, and software/hardware verification
• Logic is used to formalize query definitions in database theory
• Logic is used to formalize human inference in artificial intelligence
• Logic-based notions, such as loop invariants and pre- and postconditions, are used to prove program correctness
• Formal logic is important in electronic computer design, including efficient combinatorial networks or circuits
• Propositional logic, normal forms in propositional logic, and extensions involving predicates and quantifiers are introduced
• Predicate or first-order logic is able to express how elements in a set of values can make a statement true

Propositions

• Propositional logic begins with a proposition or statement
• A proposition is a sentence or mathematical expression that is either definitely true or definitely false, but not both
• Propositions are declarative statements that are either true or false, but not both
• Propositions are pieces of information that can be "correct" or "incorrect"
• Logic may be applied to propositions to produce other propositions
• Propositions are commonly denoted by letters like P, Q, R, S, etc
• The truth value of a proposition is either T/1 for true or F/0 for false

Examples of Propositions

• "Today is Wednesday" has a truth value
• "{0, 1, 2} \ N = ∅" has a truth value
• "The derivative of cosx is sinx" is a proposition
• "2 ∈ Z" is an example of a proposition
• "Some right triangles are isosceles" is a proposition
• "Every even number has at least two factors" is a proposition
• "2 divides every integer" is a proposition with a truth value
• "N ⊂ Z" is a proposition
• "The set {0, 1, 2} has cardinality three" is a proposition
• "Every even number has at least two factors" is a proposition
• "If a circle has radius r, then its area is (1/4)πr² square units" has a truth value
• "7 = 4" is a proposition with a truth value
• "Snow is white" is a proposition with a truth value
• "The Eagles won this year's Super Bowl" has a truth value
• "√2 ∉ R" has a truth value
• "Z ⊂ N" has a truth value
• "Every even number is divisible by 2" is a proposition
• "Every human born before 1780 has died" is a proposition

Non-Propositions

• Opinions, interrogative and imperative sentences, questions, and commands are not propositions
• "C++ is the best language" is an opinion, not a proposition
• "When is the pretest?" is an interrogative sentence and not a proposition
• "Do the following RAT" is an imperative sentence, not a proposition
• "7 + 4" is not a proposition
• "Safaricom is an excellent company" is an opinion/subjective statement, not a proposition
• "He is the new AU chair" is a statement of fact that requires context but by itself is not a proposition
• "What is the solution of 7x = −42?" is a question
• "Arsenal will win the EPL this year" is not a proposition
• "Add -7 to both sides" is a command and not a proposition

Propositions vs. Non-Propositions

• "-67" is not a proposition, but "-67 ∈ Z is an integer" is a proposition
• "Add -8 to both sides" is not a proposition, but "Adding -8 to both sides of x - 11 = 21 gives x = 7" is a proposition
• "R" alone is not a proposition, but "√3 ∈ R" is a proposition
• "What is the solution of −8x = 72?" is not a proposition, but "The solution of −8x = 72 is." is

Using Letters for Statements

• Letters such as P, Q, R, and S are used to represent specific statements
• When more variables are needed, subscripts can be used

Designating Propositions with Letters

• Propositions can be designated with letters as a shorthand
• Example: "For every integer n ≥ 1, the number 2n − 1 is prime" and designated as P
• Example: "Every polynomial of degree n has at most n roots" and designated as Q
• Example: "The function f(x) = x² is continuous" and designated as R
• Example: "Z ⊂ ∅" and designated as S1
• Example: "{0, −1, −2} \ N = ∅" and designated as S2
• Propositions can include variables, denoted as P(x) to indicate it refers to x
• "If an integer x is a multiple of 6, then x is even" can be expressed as P(x)
• A sentence whose truth depends on a variable's value is an open sentence
• The variables in an open sentence can represent any type of entity
• The function f is the derivative of the function g and can be expressed as R(f, g)
• It is true if f(x) = 2x and g(x) = x²
• It is false if f(x) = x³ and g(x) = x²

Sentences with Variables

• Sentences with variables can be denoted as R(f, g) or just R
• Use the expression R(f, g) to emphasize the sentence involves variables

Propositions in Mathematics

• Propositions are ubiquitous in mathematics
• Any proven result or theorem is a proposition
• The quadratic formula and the Pythagorean theorem are mathematical statements/propositions

Examples of Theorems as Propositions

• The solutions of the equation ax² + bx + c = 0 are x = (-b ± √(b² - 4ac)) / 2a
• If a right triangle has legs a and b and hypotenuse c, then a² + b² = c²

Existence as a Proposition

• "There exists a 100-digit prime number" is a proposition, even if we don't know if it's T or F

Truth Values

• Not every mathematical statement has a truth value
• "This statement is false" is not a proposition
• V : x ∈ S, where S = {x | x ≥ −7, x ∈ Q} is not a proposition