Table of contents
No headings in the article.
This is the part of first lecture of my series DSA: The Way I Wanted
YouTube explanation link for the same-
First, we are going to start with logic because it is a branch of mathematics and philosophy concerned with reasoning and argumentation which means that based on this reasoning we have practically working applications in our computers be it the correctness of computer programs, ensuring the quality and reliability of software systems, prove the security of cryptographic algorithms and many many more.
So, we have our reasoning in place the only thing which is left now is to validate our reasoning and for that, we need something called Proof.
Proofs, in mathematical logic, are a series of logically deduced statements used to establish the truth of a proposition or theorem (once we prove a mathematical statement is true, we call it a theorem) and the concept of a proof is used to demonstrate the correctness of algorithms and to establish the validity of logical systems.
The examples for both of them combined are in the vast array be it optimizing schedules, finding the shortest path between two points, determining the most efficient way to use resources, choosing between different options, evaluating risks and benefits, and weighing trade-offs.
Starting from the very first thing in logic is a statement, also called a proposition, which will be declarative in its nature. That is it can be either true or false. In propositional logic, we use symbols to represent propositions, and logical connectives (such as "and", "or", "not", "implies", etc.) to build complex expressions.
Examples of valid propositions-
1. New Delhi is the capital of the Indian Republic.
- 1+1 = 2 (There is a 300-page book Principia Mathematica for this)
3. Jang (my friend) was born in Manipur.
Examples of invalid propositions-
Do this!
Stand-up!
What a beautiful day!
Is the sun hot?
Two things are here- FIRST since in mathematics we usually deal with problems(statements) in the form of variables to avoid writing those lengthy statements and we are going to use p, q, r, s, . . . as the variables to represent the individual statements. It's not compulsory but is somewhat like a standard which is followed by people and even in programming we tend to use i, j, k, . . . as the inner variable in loops.
SECOND is to create new propositions which are statements constructed by combining one or more propositions. You can think of this in a way for example your friend said to you that he talked to this very girl/boy and your response to that information highly probably is no way you talked to her/him.
Let's try to represent this in the above-discussed paras -
let p be the statement said by your friend
p = I talked to this girl/boy.
let q be the statement which you said to your friend
q = You can't talk to that girl/boy.
Do you see any inference from here?
The thing which I wanna convey from here is that the very thing which you usually do with your friend is to oppose what they'd said just to tease them. But, what it actually does is this starts to build your conversation between you and your friend i.e. makes your conversation complex and fun.
This is exactly what we do here once we have our statements in place we try to make them more complex so that we can optimise and better solution in the end.
Let p be a proposition. The negation of p, denoted by ¬p
p : Jang is a good PC gamer.
¬p : Jang is not a good PC gamer.
Now, we've done converting the statements into the variables and somewhere started making statements more complex by combining more statements together.
We are now at the point of combining both of them into the tables which are known as a truth table.
A truth table is a table used in logic and mathematics to evaluate the truth value of a proposition or an argument. A truth table lists all possible combinations of truth values for the propositions involved and shows the resulting truth value of the whole statement.
A truth table has one row for each possible combination of truth values of the propositions, and the columns represent the propositions involved in the statement. The last column of the truth table contains the true value of the whole statement, based on the truth values of the propositions.
Here, is the Truth table for the Negation of a proposition.
p ¬p
T F
F T
Now, if you pay a little attention to your own language there are always some connectivities so that you can create more complex propositions.
Such basic two are also available here and they are and & or.
They are represented by ∧ & ∨(also known as conjunction & disjunction)
In the English language connectivity or is taken in two ways what I mean is sometimes when it's used it can also include both sentences i.e inclusive or sometimes it refers that only one sentence out of the connected two sentences can be valid not both at the same time i.e. excluding.
So, the inclusive or is represented with the same symbol above but to make a distinction for the exclusive or we use the symbol ⊕
Now, we have seen conjunction, disjunction and Xor it's time to see -
Conditional statements are nothing but if p then q which means the first thing only happens when the sufficient condition of the next dependent statement occurs and this is represented as p → q.
There are some variations to the same -
“if p, then q” “p implies q” “if p, q”
“p only if q” “p is sufficient for q”
“a sufficient condition for q is p” “q if p”
Here's an example of a conditional statement:
"If it rains, then I will carry an umbrella."
In this example, the event is "it rains" and the consequent is "I will carry an umbrella." If it rains, then the event is true and the whole statement is true. If it doesn't rain, then the event is false and the whole statement is true.
There are three more things which are related to this Converse, Contrapositive and Inverse. Let's look at them -
The proposition q → p is called the converse of p → q.
The contrapositive of p → q is the proposition ¬q → ¬p.
The proposition ¬p → ¬q is called the inverse of p → q
Here's an example to illustrate the concepts of converse, contrapositive, and inverse:
"If it is raining, then the streets are wet."
Converse: "If the streets are wet, then it is raining."
Contrapositive: "If the streets are not wet, then it is not raining."
Inverse: "If it is not raining, then the streets are not wet."
There is something also called a biconditional statement and it's represented by p ↔ q. It's true when both p & q have the same truth values.
Predicates and Quantifiers are fundamental concepts in mathematical logic.
A predicate is a function that maps elements of a set to truth values (true or false).
Predicates can be used to describe the properties of elements in a set. For example, the predicate "x is an even number" can be applied to elements of the set of integers to determine whether they are even or odd.
Quantifiers are symbols used to express the number of elements in a set that satisfy a predicate. The two most common quantifiers are the universal quantifier (∀) and the existential quantifier (∃).
The universal quantifier (∀) expresses that a predicate is true for all elements in a set. For example, "for all x in the set of natural numbers, x > 0" can be expressed as ∀x (x > 0).
The existential quantifier (∃) expresses that there exists at least one element in a set that satisfies a predicate. For example, "there exists a natural number x such that x > 10" can be expressed as ∃x (x > 10).
Rules of inference
why rules of inference are needed in logic and proofs?
Rules of inference are needed in logic and proofs because they provide a systematic method for deducing new conclusions from given premises. These rules are based on logical relationships between propositions, and they allow us to determine whether a conclusion logically follows from the premises.
By using rules of inference, we can build logical arguments that are valid and can be used to prove theorems, solve problems, and make decisions.
This is taken from my blog - devanshvarshney.blogspot.com