Propositional Logic: Fundamentals and Applications

By Fouad Sabry

What Is Propositional Logic

The field of logic that is known as propositional calculus. There are a few other names for it, including propositional logic, statement logic, sentential calculus, sentential logic, and occasionally zeroth-order logic. It examines propositions as well as the relations that exist between propositions, as well as the formulation of arguments that are founded on propositions. By combining individual statements with various logical connectives, one can create compound propositions. Atomic propositions are those that don't have any logical connectives in them, as the name suggests.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: Propositional calculus

Chapter 2: Axiom

Chapter 3: First-order logic

Chapter 4: Modus tollens

Chapter 5: Consistency

Chapter 6: Contradiction

Chapter 7: Rule of inference

Chapter 8: List of rules of inference

Chapter 9: Deduction theorem

Chapter 10: Theory (mathematical logic)

(II) Answering the public top questions about propositional logic.

(III) Real world examples for the usage of propositional logic in many fields.

(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of propositional logic' technologies.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of propositional logic.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jun 24, 2023

Book preview

Chapter 1: Propositional calculus

Ch.

Propositional logic does not deal with non-logical objects, predicates about them, or quantifiers, in contrast to first-order logic. However, first-order logic and higher-order logics contain all of the propositional logic's machinery. In this sense, first-order logic and higher-order logic are built on propositional logic.

Natural languages contain logical connectives. Examples include and (conjunction), or (disjunction), not (negation), and if in English (but only when used to denote material conditional).

Here is an illustration of a straightforward inference that falls under the purview of propositional logic:

First premise: If it's raining, it must be cloudy.

2. That it is raining.

Finally, it's cloudy.

The conclusion and the premises are both propositions. The conclusion flows from the premises, which are assumed, when modus ponens (an inference rule) is used.

This inference can be restated by substituting statement letters for the atomic statements because propositional logic is not concerned with the structure of propositions beyond the point where they can't be further divided by logical connectives. Statement letters are interpreted as variables that represent statements:

Premise 1: P\to Q

Premise 2: P

Conclusion: Q

The following sentence provides a short method to state the same:

{\displaystyle {\frac {P\to Q,P}{Q}}}

The above symbolic expressions can be seen to correspond exactly with the original phrase in natural language when P is translated as It's raining and Q as It's cloudy. Additionally, they will match any other inference of this kind, which will be accepted on the same grounds as this inference, and.

A formal system that interprets formulas of a formal language to express propositions can be used to study propositional logic. Some formulas can be obtained using an axioms and inference rules system. These derived formulas are known as theorems and can be understood as true statements. A derivation or proof is a created set of these formulae, the last formula of which is the theorem. The derivation might be seen as evidence for the theorem's associated statement.

When formal logic is represented by a formal system, only statement letters (usually capital roman letters such as P , Q and R ) are represented directly.

The system does not address the natural language statements that result from their interpretation, Furthermore outside the formal system itself is the relationship between the formal system and its interpretation.

Formulas are regarded as having precisely one of two potential truth values, the truth value of true or the truth value of false, in classical truth-functional propositional logic. Both the law of excluded middle and the bivalence principle are upheld. Systems that are isomorphic to truth-functional propositional logic are referred to as zeroth-order logic. Alternative propositional logics are nevertheless conceivable. See Other logical calculi below for further information.

Although earlier philosophers had hinted at propositional logic—also known as propositional calculus—Chrysippus refined it into a formal logic (Stoic logic) in the third century BC. The origin of truth tables, on the other hand, is unknown.

Within Frege's works

A calculus is a formal system that includes a collection of syntactic expressions (well-formed formulas), a distinguished subset of these expressions (axioms), and a collection of formal rules that define a particular binary relation on the space of expressions that is meant to be understood as logical equivalence.

The rules, known as inference rules, are normally designed to be truth-preserving when the formal system is intended to be a logical system and the expressions are supposed to be understood as assertions. In this situation, formulae representing true assertions can be derived (or inferred) from provided formulas expressing true claims by using the rules, which may include axioms.

The set of axioms could be countably infinite, nonempty, or empty (see axiom schema). The language's phrases and well-formed formulas are defined recursively by a formal grammar. Additionally, a semantics that defines truth and valuations may be provided (or interpretations).

A propositional calculus's language consists of

a collection of primitive symbols, often known as placeholders, proposition letters, variables, or atomic formulae, and

a group of operator symbols that can be used as logical operators or logical connectives in different ways.

Any atomic formula or formula that can be constructed from atomic formulas using operator symbols in accordance with the grammar rules is considered to be well-formed.

Certain propositional constants are distinguished by mathematicians from others, propositional variables, and schemata.

Constants of propositions represent a specific proposition, while the set of all atomic propositions comprises propositional variables.

Schemata, however, range across all hypotheses.

Propositional constants are frequently represented as A, B, and C, variable propositions by P, Q, and R, Greek letters are frequently used in schematic lettering, most often φ, ψ, and χ.

An example of a typical propositional calculus is given below. There are numerous formulas that are all roughly comparable but varied in the specifics of:

their dialect (i.e., the particular collection of primitive symbols and operator symbols), the collection of axioms, distinct formulas, and

the collection of inference laws.

A 'propositional constant' is a letter that can be used to represent any given proposition, similar to how a letter in mathematics is used to represent a number (e.g, a = 5).

Every claim needs exactly one of the following two truth-values: valid or invalid.

For example, P should stand for the assertion that it is raining outside.

If it's raining outdoors (P), then this will be accurate, and false otherwise (¬P).

Next, truth-functional operators are defined, putting negation first.

¬P represents the negation of P, This may be considered the denial of P.

In the aforementioned instance, ¬P expresses that it is not raining outside, Alternatively by the following, more common translation: It is not true that it is raining outside. P is true when, ¬P is false; and if P is untrue, ¬P is true.

The result is, ¬ ¬P always has the same truth-value as P.

A truth-functional connective called conjunction creates a proposition from two simpler propositions, for example, P and Q.

The conjunction of P and Q is written P ∧ Q, and declares that each is accurate.

We read P ∧ Q as P and Q.

For any two hypotheses, There are four possible truth value assignments:

P is true and Q is true

P is true and Q is false

P is false and Q is true

P is false and Q is false

In example 1, the conjunction of P and Q is true, and otherwise is false.

P is the claim that it's raining outdoors, and Q is the claim that a cold front has passed. Kansas, P ∧ Q is true when it is raining outside and there is a cold-front over Kansas.

Unless it is raining outside, then P ∧ Q is false; and if Kansas does not experience a cold front, then P ∧ Q is also false.

In that it creates a proposition out of two less complex propositions, disjunction is similar to conjunction.

We write it P ∨ Q, and P or Q are displayed.

It indicates that P or Q must be true.

Thus, the situations mentioned above, P and Q are always disjunct, with the exception of example 4.

Using the prior instance, The disjunction states that either it is pouring outdoors or it is not, Maybe a cold front is passing across Kansas.

(Note, This disjunction is meant to imitate how the English word or is used.

However, It resembles the inclusive or in English the most, which can be used to indicate that at least one of two statements is true.

It differs from the exclusive or in English, which states that exactly one of two propositions is true.

Alternatively put, When both P and Q are true, the exclusive or is false (case 1), and similarly, when both P and Q are false, is false (case 4).

You can choose between a bagel and a croissant, as an illustration of the exclusive or, however not both.

naturally occurring language, given the right circumstances, The omission of the phrase but not both is inferred.

In mathematics, however, The word or is always inclusive; If exclusivity or is intended, it will be made clear, (Possibly using xor

Additionally, the material conditional connects two more basic hypotheses, and we write P → Q, that says, If P, then Q,.

The antecedent is the statement to the left of the arrow, and the right-hand proposition is known as the consequent.

(Conjunction and disjunction don't have such names, They are commutative operations, thus.) It states that anytime P is true, Q is also true.

Thus P → Q is true in every case above except case 2, because only in this situation is P true but Q false.

Citing the instance, Q expresses that if P, then it is raining, Afterward, a cold front forms over Kansas.

Physical causality and the material conditional are frequently mistaken terms.

The substantive condition, however, merely compares two propositions based on their truth values, which is not a cause-and-effect relationship.

Literature debates whether the material implication constitutes logical causation.

Biconditional connects two more straightforward ideas, and we write P ↔ Q, This reads, P only if and when Q..

It indicates that the truth-value of P and Q is the same, in instances 1 and 4, and.

If and only if Q is true, then P is true, and otherwise is false.

Examining the truth tables for these various operators and the analytic tableaux approach is quite beneficial.

Truth-functional connectives close propositional logic.

Thus, to sum up, for any proposition φ, ¬φ is also a proposition.

Likewise, for any propositions φ and ψ, φ ∧ ψ is a proposition, likewise for disjunction, conditional, and biconditional.

This suggests that, for instance, φ ∧ ψ is a proposition, Consequently, it can be connected to another proposition.

In order to illustrate this,, To show which proposition is connected to which, we must use parenthesis.

For instance, P ∧ Q ∧ R is not a well-formed formula, because we do not know if we are conjoining P ∧ Q with R or if we are conjoining P with Q ∧ R.

Thus we must write either (P ∧ Q) ∧ R to represent the former, or P ∧ (Q ∧ R) to represent the latter.

Taking into account the truth conditions, We can observe that the truth requirements for both formulations are the same (will be true in the same cases), in addition to the fact that every proposition created by arbitrary conjunctions will have the same truth criteria, regardless of where the parentheses are placed.

Conjunction is hence associative,, however, One shouldn't assume parenthesis are always useless.

For instance, the sentence P ∧ (Q ∨ R) does not have the same truth conditions of (P ∧ Q) ∨ R, Thus, they are distinct phrases that can only be identified by the parentheses.

The above-mentioned truth-table technique can be used to confirm this.

Please take note that for every arbitrary quantity of propositional constants, A limited number of instances that list potential truth values can be created.

Truth-tables