Lecture 1 - Propositional Logic

Name: Lecture 1 - Propositional Logic
Uploaded: 2007-12-04T11:14:05.000Z
Duration: 1 h 52 min 48 s
Description: Discrete Mathematical Structures

Introduction to Discrete Mathematics

Overview of the Course

The course focuses on discrete mathematical structures, aimed at B. Tech or B.E. students in computer science during their second semester.

Discrete Mathematics studies abstract mathematical models dealing with discrete objects and their relationships, including sets, permutations, and graphs.

Importance of Studying Discrete Mathematics

Understanding basic mathematical concepts is crucial for various fields in Computer Science; brief mentions in textbooks may not suffice for comprehensive understanding.

The course aims to develop a habit of thinking mathematically among students, enhancing their grasp of other computer science subjects.

Applications of Discrete Mathematics

Relevance Across Computer Science Fields

Concepts from discrete mathematics are applicable in programming for proving program correctness and artificial intelligence through logic principles like Prolog.

In computer networks, graph theory and finite state automata (FSA) are essential; these concepts also appear in compilers and hashing functions.

Course Structure and Topics Covered

Breakdown of Topics

The first nine lectures will focus on Logic; subsequent topics include sets, relations, functions, graphs, combinatorics, recurrence relations, algebras, and FSA.

Each topic is designed to build upon the previous one; for example, after learning about graphs (lectures 14-17), the course revisits properties of relations (lectures 18-23).

Learning Expectations

Students are expected to have reasonable mathematical maturity akin to that of a high school student; no prior knowledge is required.

Recommended Textbooks

Suggested Reading Materials

Key textbooks include "Elements of Discrete Mathematics" by C.L. Liu and "Discrete Mathematical Structures with Applications to Computer Science" by Tremblay and Manohar.

Other notable books: "Discrete Mathematics in Computer Science" by Stanat & McAllister and "Mathematical Theory of Computation" by Manna.

Introduction to Logic

Significance in Computer Science

Logic is fundamental for proving program correctness and is applied across databases (relational algebra/calculus), as well as artificial intelligence reasoning tasks.

Lecture Breakdown on Logic

The first two lectures will cover Propositional Logic followed by Predicate Logic; additional topics include Logical Inference, Resolution Principle, Methods of Proofing Programs Correct.

What is Propositional Logic?

Understanding Propositions

A proposition is defined as an assertion that can be either true or false, distinguishing it from questions and orders.

Truth values are assigned to propositions: false is denoted by 0 and true by 1. An example of a proposition is "4 is a prime number," which has a truth value of false.

Examples of true propositions include "3 plus 3 equals 6." Non-propositions include statements like "X plus Y greater than 4," which depend on variable values for their truth value.

Characteristics of Propositions

Individual variables (like X and Y) do not have unique truth values; they depend on the assigned numbers.

Questions (e.g., "Are you leaving?") and commands (e.g., "Buy 4 books.") are not assertions, hence cannot be classified as propositions.

The statement "This statement is false" exemplifies a paradox known as the liar paradox, which cannot be assigned a definitive truth value.

Propositional Variables and Connectives

Propositional variables (P, Q, R) represent arbitrary propositions with unspecified truth values. They can take on specific propositions similar to how variables in algebra work.

Logical connectives such as AND, OR, and NOT allow for the combination of propositions into compound statements. For instance, P AND Q requires both P and Q to be true for the compound statement to hold true.

Truth Tables for Logical Connectives

The truth table for AND shows that P AND Q is only true when both P and Q are true; otherwise, it’s false.

In contrast, the OR connective allows for P OR Q to be true if at least one of P or Q holds true. This includes cases where both are true.

Unary Operator NOT

The NOT operator negates the truth value: if P is false, then NOT P becomes true. For example, if John is not 6 feet tall represents NOT P.

Exclusive OR Operator

The Exclusive OR operator indicates that its compound statement will only be true when exactly one of its components is true—this differs from inclusive OR where both can also yield a true result.

Understanding Logical Statements and Their Implications

The Nature of Logical Statements

A logical statement can be true or false, but if both components are true or both are false, the compound statement is considered false. For example, "John is 6 feet tall" and "there are 4 curves in the bond" can both be true simultaneously.

The term "Exclusive or" (XOR) is used when only one of two statements can be true at a time. In contrast, "inclusive or" allows for both statements to be true.

Care must be taken when converting English sentences into logical notation; distinguishing between inclusive and exclusive 'or' is crucial for accurate representation.

Well Formed Formulas in Propositional Logic

A well formed formula (wff) in propositional logic connects variables logically. Examples include P and Q, P or Q, and P Exclusive or Q.

Two additional operators in logic are implication (P implies Q) and equivalence. Notation may vary across texts, so it's important to recognize different representations.

Understanding Implication

In an implication statement (P implies Q), P is known as the premise or antecedent while Q is referred to as the conclusion or consequence.

The truth table for implications shows that it’s only false when the premise is true and the conclusion is false; otherwise, it remains true under all other conditions.

Differences Between Greek and Indian Logic

Greek logic permits unrelated premises and conclusions within implications; for instance, “the moon is made of cheese” leading to “the earth is not round” can still yield a true implication despite lack of relation.

Conversely, Indian logic emphasizes relatedness between antecedents and consequences—e.g., falling into a lake leads to getting wet—highlighting a correspondence that Greek logic does not require.

Sufficient Conditions vs Necessary Conditions

Various interpretations exist for implications: "if P then Q," "P only if Q," etc., which relate back to concepts of sufficient conditions (P being enough for Q).

The converse of an implication reverses its order (Q implies P), while the contrapositive negates both sides (NOT Q implies NOT P). These relationships help clarify logical structures in proofs.

Truth Tables Explained

Constructing truth tables involves listing all possible values for variables like P, Q, R, etc., with each variable assigned either true (1) or false (0).

For multiple variables—like four—the number of rows doubles exponentially based on combinations; thus with four variables there would be 16 possible outcomes represented in the truth table.

Understanding Propositional Logic and Truth Tables

Basics of Truth Tables

When dealing with N propositional variables, a truth table will have N columns for the variables, followed by additional columns for expressions. For two variables, there are two columns dedicated to them.

There are 2^N possible assignments of truth values for these variables, resulting in 2^N rows that represent binary numbers from 0 to 2^N - 1.

Implications and Contrapositives

The expression "NOT Q implies NOT P" is the contrapositive of "P implies Q." The implication is false only when the premise is true and the conclusion is false.

Both implications yield identical truth values; thus, they can be used interchangeably in logical statements.

Understanding Equivalence

Logical equivalence is denoted by a double arrow (↔), indicating that P is equivalent to Q if both have the same truth value—either both true or both false.

This concept relates closely to Boolean algebra but focuses on equivalence and implication rather than just AND/OR operations.

Constructing Truth Tables

To construct truth tables for expressions like "Q and NOT P implies P," start with k columns for k variables. Each row represents all possible combinations of variable assignments.

For example, with two variables (P and Q), you would list combinations: 00, 01, 10, 11. Then evaluate expressions based on these combinations.

Evaluating Complex Expressions

In evaluating "P and Q or NOT R is equivalent to P," three variable columns are needed. You must calculate intermediate results like "P and Q" and "NOT R."

The final column compares results from both sides of the equivalence; they are equivalent when their outputs match across all rows.

Tautologies in Propositional Logic

A tautology is a propositional form that remains true regardless of the truth values assigned to its variables. An example includes "P or NOT P," which always evaluates as true under any assignment.

Understanding Tautologies, Contradictions, and Contingencies

Definitions of Key Concepts

A tautology is defined as a propositional form that is true for all possible values of its variables.

A contradiction (or absurdity) is a propositional form that is always false; an example being the expression P and NOT P.

A contingency refers to a propositional form that can be either true or false depending on the values of its variables.

Examples and Truth Tables

Examples of contingencies include expressions like Q and NOT P implies P and Q, which can be true in some cases but false in others.

To determine if a propositional form is a tautology or contradiction, one can construct a truth table. If the last column shows all 1's, it’s a tautology; if all 0's, it’s a contradiction; mixed results indicate contingency.

Logical Identities and Simplifications

Idempotence Laws

The idempotence law states that P is equivalent to P or P; thus, repeating the variable does not change its value.

Similarly, for conjunction: P and P simplifies to just P.

Commutative Laws

The commutative law allows interchangeability in logical operations: Q or P equals P or Q.

This applies similarly to conjunction: P and Q equals Q and P.

Associativity and Parentheses

Associative Laws

The associative law indicates that grouping does not affect the outcome: (P or Q) or R equals P or (Q or R).

For conjunction: (P and Q) and R equals P and (Q and R), allowing flexibility in expression without changing meaning.

Importance of Parentheses

Implication lacks associativity; thus parentheses are crucial for clarity. For instance, distinguishing between P implies (Q implies R) versus (P implies Q) implies R.

De Morgan's Laws

Transformation Rules

De Morgan's laws state that NOT(P or Q) transforms into NOT(P) AND NOT(Q).

Conversely, NOT(P AND Q) becomes NOT(P OR NOT(Q)), demonstrating how negation interacts with logical operators.

Distributive Laws

Distributing Operators

The distributive law states that P AND (Q OR R)equiv (P AND Q )OR (P AND R).

Special Cases with True/False Values

When one operand in an OR operation is true (P OR 1), the result remains true.

In an AND operation (P AND 1), if Pis true then it holds its value; otherwise it's false.

Tautologies & Contradictions Recap

Summary of Core Principles

Tautologies such as P OR NOT(P), are always true while contradictions like P AND NOT(P), are always false.

Logical Implications and Equivalences

Understanding Logical Statements

The statement "P implies Q" can be expressed as "NOT P or Q," illustrating a fundamental equivalence in logic.

The equivalence of "P is equivalent to Q" can be represented as both "P implies Q" and "Q implies P," highlighting the bidirectional nature of this relationship.

The expression "P and Q implies R" is equivalent to saying "P implies (Q implies R)," demonstrating how implications can be nested within each other.

The formulation "P implies Q and P implies NOT Q" leads to the conclusion known as absurdity, which is crucial in proofs by contradiction.

A previously discussed equivalence states that "P implies Q" can also be framed as "NOT Q implies NOT P," reinforcing the concept of contrapositive reasoning.