00:00

hi everyone welcome back this is dave in this video or this episode inference

rules fundamentals explained so in this episode you’ll learn what

inference rules are and why they are fundamental

so before we get started i wanted to mention that this video is part of the

series logic and mathematical proofs in-depth tutorials for beginners the

link for the full playlist is below in the description

so in this uh episode we’re going to talk about mathematical proofs

and we’re going to talk about inference rules and then um are we going to start

writing proofs well let’s get go ahead and get started and find out [Music]

all right so first off we’re going to have some background information about

what proofs are before we start writing them

um and so let’s put this together and let’s try to answer this question what

00:01

is approved so here we’re going to have a mathematical proof or just proof for

short so we’re going to mean the assertion that a certain statement or the

conclusion follows from other statement the premises

so in the last episode we talked about what a propositional consequence is so

we’re we’re going to go and we’re furthering that idea here so proof was

said will be said to be logically valid if and only if the conjunction of the

premises implies the conclusion so if all the premises are true then the

conclusion must also be true so we started illustrating valid

arguments uh last time and in this video we’re going to talk about inference

rules so to determine whether a mathematical

proof is valid we must accomplish two goals first off we need to know if we

have a valid argument or not so that’s why we spent a whole episode the

previous episode on talking about whether or not an argument is valid

00:02

and then we need justifications for each

statement and so we’ll see how inference rules can

bring all this together so we can start writing mathematical proofs

so it’s important to realize that a logical argument depends upon its form

in that it does not matter what the components of the argument are

so right here it doesn’t matter what the p q’s and r’s represent

they can represent anything you can be talking about number theory real

analysis geometry trigonometry you know the p’s and q’s can be from any field of

mathematics but we’re going to be looking at the

form the form is the if then and then we have an and here right

so so since the implication right here this one and this one so we have an and

right here and then we have the if then so we have an implication here so this

is a tautology right here so this is called a valid argument this argument

right here and can be proven using a truth table

00:03

and we’ve uh did a previous uh episode where we talked about what truth tables

are in fact we had several of them and we even did one where we were true

tables in python and so we’ll see some more examples of that here

so indeed this is a valid argument regardless of whatever p q and r are

all right so proof demonstrates that the conclusion must happen is a

consequence of the premises so these are

the premise right here or you could call these premises

this is the whole premise right here and this is the conclusion right here

all right so why do we use inference rules so let’s talk about that

so an argument is a collection of statements that are broken up into

premises and a conclusion so we often write it like this right

here as we did last time p1 p2 this is in column format

and then we have pk the last one and then we say therefore and some people

00:04

that may not even write that symbol there but sometimes i do so we say

therefore and then we have a conclusion so all these combined together with an n

this is our hypothesis and this is our conclusion

now of collection of statements like p1 through pk in which there’s no

connection with the queue if there’s no connection with the queue

so it’s not going to be much use you may

have a valid argument but it’s not going to be very helpful or useful if there’s

no connection between the piece and the queue that’s where you get the most

connection or that’s where you get the most value

so our argument is called valid if the conclusion necessarily follows from the

premises and we make sure that happens by putting all of these with an and and

putting all this into an implication if all of these happen then q has to happen

so by showing the statement is the tautology

which we could accomplish using a truth table but this method would

00:05

neither be pleasant nor helpful so for example what if this was p 10 [Music]

so what if you had 10 statements right and a proof using 10 statements

isn’t that long there’s lots of proofs out there that are hundreds even

thousands of statements long so you know you would never try and go

to make a true table what is p1 p2 p3 and start building all of these columns

out here right and so then our last column would be the all of these imply

q right so that would be a lot of columns a lot of variables so that would be

that’s intractable uh generally speaking all right so how we gonna do this right

so first for complicated arguments the um the truth table would be too large so

second using a true table gives no intuitive insight into why the argument

is valid so i’ve touched upon this in the last video i just certainly want to

00:06

re-emphasize that so finally when proving mathematical

statements we often use quantifiers which make which makes truth tables

virtually impossible to use so for these three arguments right here

is y is basically why we don’t use true tables when we’re making mathematical

proofs so mathematical proofs are never and i put parentheses around the never

because there may be some people who are interested in computational style

mathematics and perhaps they might use true tables but the working

mathematician or the working scientist or the working engineer

this is pretty much a given here so instead of using true tables we will

try to justify the valid arguments by making use of

inference rules so we’re going to think of inference rules as little tiny

building blocks when you’re going to build more complicated arguments and so

the inference rules keeps us on track it makes sure that whatever we’re saying

00:07

whatever is um you know being deduced along the trail of arguments

that we’re going to stay sound we’re going to stay logically sound and we’re

going to and we’re going to have a valid argument at the end

all right so these simpler implications or inference rules are already known

and they’re building blocks for more complicated arguments so in doing so

we’re going to write our mathematical proofs so our mathematical proofs is

more than just a collection of statements it’s a collection of

statements and its invoking inference rules to keep our argument sound invalid

all right so let’s look at some inference rules here now let’s go down

here and these are going to be our most common inference rules

so this is a valid argument right here and we can show that by looking at this

tautology and this argument is called addition

and as you can see it’s a very simple small type of you know this is not a

00:08

long complicated argument it’s just got one hypothesis and one conclusion but

this is a tautology if you know that p is true

then you can conclude that p or q has to be true one or the other has to be true

perhaps both but you know that p is true so you know that the or is true so this

is an inference rule it’s called the addition inference rule and so we

occasionally use this so this is called the simplification rule

if you know that p and q are true then it must follow that p is true right

so if you know both of them are true then therefore p has to be true and you

can determine that that’s a valid argument by making this

tautology right here by proving this tautology right here

this is called the simplification now we have this argument here p

and then we have a q we know both of those are true therefore

the p and q has to be true and this is called the conjunction rule

00:09

all right so we got some more over here um so these are this one’s called the

modest bonus and this one is by far the most popular

so it says if you know p is true and if you know that p implies q is true

this whole implication is true then you can conclude that q has to be true

again we can prove this is valid looking at a true table there

so this is moz tallness and so it says not q and p implies q

and then we can conclude that not p is true then we have the hypothetical

and then we say p implies q and q implies an r

therefore we can conclude that p implies r

so if you know the transitive rule from from order theory then

this looks a lot like that this is the tautology right here

00:10

we have our last one right here um p or q assuming that’s true assuming not p is

true then we can conclude that q is true and this will be our disjunctive

and so let’s look at some proofs here so we’ll try to make this bigger for us

oops wrong one here um let’s go down here and use this mouse here

and now we’re going to look at setup here and we’re going to do this python here

again so i’m going to include this python file that we’ve been doing in all

of our episodes so far so we’re going to import that python

file there and we’re going to declare some variables

and then we’re going to look at our inference rules here so we have the addition

so here’s the addition which you can see right here

and we’ll print out that truth table there we can see it’s a tautology

00:11

we can see the simplification is a tautology we can see the conjunction in

synthetology right here we can check out modest ponis

and see that that’s a tautology right there we can look at monotonous we can see

tautology and then we’ll look at these last two here and we can

double check that there are all tautologies here all right

so good they’re all tautologies as we can see right here they’re all

tautologies let’s go back here and so we checked all these our

tautologies right here and we’re going to use these as building blocks when we

start writing proofs so as you can see these are all very short these are only

two hypotheses long right here and this one’s two and two and this one’s got two

and this one’s got two so these are small little tiny arguments and the more

you start writing proofs the better you get at using these um

00:12

so yeah so i mean just takes years of experience and then as you

keep writing more mathematical proofs these become very easy to use so this is

the major building blocks step by step by step we can build a proof so

um let’s go here is the shortest proof always the best proof

so before we start writing proofs i want to say that you know writing proof

because it’s not brute force like a truth table we’re just going through

line by line row by row and and doing calculation

mathematical proof is a creative process

so sometimes you’ll get into a proof and you’ll prove something and you realize

oh you had some additional steps you didn’t need maybe you need to write a

first draft maybe you need a second draft

and so the shortest proof may not always be the best proof and sometimes it is

sometimes it isn’t but proofs um you know usually are

00:13

written for an audience and so you want to write it a nice elegant proof for

whatever audience you have maybe your audience is fellow students maybe your

audience is the general public maybe your audience is other specialized

mathematicians so you always want to think of the best proof and so i wanted

to just kind of give a a quick theorem here which will kind of help us

understand how this is uh sort of an art form and

a form of art and it’s not just a technical brute force calculation like

truth tables would be so to try to get a feeling for for that

i came up with this theorem here to help us try to understand how sometimes when

you write a proof you may have extraneous information in there but that

extra information may be insightful or enlightening to your readers so you may

include it or maybe you don’t it just depends upon who your audience is and

and what you’re doing so this theorem says the following

suppose a statement r is a consequence of the premises

00:14

right and so you know that let’s just pause right there before the end just

because i don’t want to lose anybody so what does that what does that right

there mean so p1 and p2 and all the way to pk

no parenthesis there we’ve got an and and a pk here

so suppose statement r is a consequence so we know what the word consequence

right here means that has a technical meaning that we talked about in the last

video and what that means is that this right here is a tautology so is a

tautology so that’s what the first that’s what we’re supposing here suppose

this is a tautology or it said a different way suppose the statement r is

the consequence of the premises and also suppose we have we’re assuming

another thing another statement q is a consequence of the same premises and are

so this the second part the end this second part right here

00:15

is assuming that p1 p2 all the way to pk and r so and r and

q is the consequence of that so q is a consequence of all these and so that

means that it’s a tautology here so we’re assuming

so the first sentence is assuming that this is a tautology and this is a

tautology and so what the conclusion is so then so we can conclude then

that q is a consequence of just these p1 and pk is a tautology

so written in symbol form or if this is a tautology and this is

the tautology then it has to follow that

this right here is a tautology and so in some sense this r right here was

00:16

not necessarily needed or maybe it was needed or maybe the r was the insight

into your argument because because we don’t know what the ps and q’s are

they could be mathematical statements from any field of mathematics geometry

number theory whatever so whatever we’re mathematics that we’re working on

we use this r here maybe the arc gave us some kind of insight because we’re able

to establish that this was a tautology and we’re able to establish that this is

the tautology or these are valid arguments we’re able to prove this we’re

able to prove this whatever method is possible then we

would be able to prove this right here so you could think of this r as

insightful or redundant or whatever you’re thinking is but sometimes the the

mathematics is a creative process where you know you could prove this as a

tautology maybe without using the r but maybe you want to include the r so

those type of arguments is really a meta meta argument in terms of the style of

00:17

your proof style of your proof is also to be taken into consideration because

it goes towards being a writer as a as a writer of mathematics you

always try to take into account your audience for example the audience for

this video are beginners um well beginners who have watched the first

couple videos in the series right in any case

let’s go and see why this might be true here so let’s look at a proof right here

let me erase this right here now this is not a rigorous proof

it’s just kind of to get us into the feeling for it so for rigorous proof we

need to show that this right here so this is the first one right here

that all of these imply are and then we have the second statement right here

all of these right here and r implies a q

and then all of that implies that q is a consequence of just these so we need to

00:18

show that all this right here is a tautology so before we go do that

let’s take a look at if we can here maybe an example right here

so see if we can go back down here and look at an example

so what i’m going to do here in this example over here

i’m going to use a p a capital p and the capital p is going to represent the

statement p1 and p2 so this will be our definition of capital p p 1 and p 2 and

m p k whatever is given to us this will be our capital p

and so when we look back at this form right here we have

this will now look like p capital p implies an r

and then we have parentheses with an and and then we have p and r

00:19

let’s use a little r here and let’s make that look like a capital p so that’s p

p implies r and p and r implies a q and then all of that implies a

and then this this is a capital p here implies a q

so we need to show that this is the tautology and all i’m doing is a

substitution i’m just calling all that a capital p

and i’m calling it all a capital p and all calling it all a capital p here we

need to show this as a tautology right here so i wanted to do that real quick

with this right here [Music] so here we have the um p implies an r uh

and p and r implies a q and then both of those with an and

implies a p implies a q here so we’ll go and execute that and we see

that it’s it’s in fact a tautology so this right here

00:20

you can think about it as a tautology now just for fun i went and did some more

so i did a p1 and p2 so instead of using a capital p like right here

i’m going to use a p1 and p2 and then i use it again here p1 and p2 and the p1

and p2 and you can see right here this is a tautology

and then i went and did it for p1 and p2 and p3 and then i did it again here

and so you know if you use the capital p and substitute it all

or if i just say p1 and p2 and p3 and use that that’s what i did right

here but you see that you cannot just do all of them it just gets to be too many

but um [Music] we could [Music] figure a way to

there it goes you can see they’re all trues and that this is a um tautology here

anyways let’s go back here and let’s look right here

00:21

and let’s get rid of all this stuff right here so we need to show that this is a

tautology for any k for any number of these that we want

so we looked at if there’s one two or three right

to understand why this is cystology let p be the variable for

so capital p or lowercase p but you know use the variable for all of these and

consider the true table for this right here so remember the true table for an

implication right so we have true false true false true true false false

we have true false true true so let’s keep that in mind here

now in any row where p is false right here where p is false right here these

are automatically true right here so um and that’s just by definition of the

connective right by implication right so in any row where p is true so now i’m

00:22

looking at these two rows here and any row where p is true

r must also be true so if we’re looking at p implies a q here

but we’re looking at this whole table right here um you know

in any row where p is true r must also be true since this right here is a

tautology so you know and why why is this a tautology because we’re saying

that r is a consequence of the premises so that

means that all these p1 and p2 and pk all of them implies r is a tautology and

so that’s why this sentence right here is true

but you know when we start looking at the full table here

p implies an r and p and r implies a q implies p implies q

then you’ll start to realize that we need to look at the rows for p where

00:23

it’s true um so let’s go back here and look at that real quick

we have it right here and let’s zoom in real quick

maybe one more time there we go so we looked at um

you know this whole thing right here this whole implication right here

anytime p is false we already know that these are true right here

and when the p is true then we have to look at the r’s here

so when the p when the p’s are true and in any row where p is false

this right here is true by definition now any row where p is true

r must also be true because this is a tautology right here so in any row where

00:24

p is true r must also be true so that comes from looking at this right here as a

tautology so let’s just put it over here i guess p implies an r

so we know that this is a tautology right here so um this right here

yeah so when this is so this is a tautology so that means if i get true

true true true from all of this but the only way these can be all trues is if

um the you know because the only way an implication is not going to be true is

if we have a true false so you know if we know that p’s are trues

here then the r must also be true because we have a tautology for

this right here so if maybe if i can put it out here p q sorry pr

and p implies an r so since we know that this is the tautology here

00:25

and we’re only looking at the cases right here where p is true so

can any of these r’s so i’m trying to make sure that we understand this

sentence right uh this sentence right here in any row where p is true

r must also be true right so because if r is false then this implication won’t

be a tautology right here because this will lead to a false so we

have to have it true right here right so i’m trying to write an argument out

that is substitution for building the truth table for this right

here so p implies an r and and then p and r implies a

q and then all of that implies so if we were to try to build out the

true table for this you would come across these rows right

here where the p’s are trues and we’re not going to have any problems

where the p is falses where any of this is false right here

00:26

okay so i hope that helps you understand this sentence right here

where if if p is true r must also be true because we’re assuming that this is

a tautology because we’re assuming that r is a consequence of the these uh

premises right here so this has to be all trues right here whenever p is true so

this r’s right here have to be true all right so now for the next line um

[Music] but since this right here is always true so why is this always true

right so that’s um p and r implies q in other words we’re

saying over here we’re assuming that q is a consequence of these so we’re

assuming that this is always true so this guarantees in any row where p is

true q must also be true because this is a tautology right here right so if p is

true r must be true so this is true and for the whole implication to be a

00:27

tautology then q must also be true all right so this is basically

the argument right here now if you’re not convinced of this argument right

here you can go line by line and check that out and see

that that truth table will always go but i think you can try to get it from

this argument right here [Music] and so that is it from this video right here um

you know make sure um and study these uh episodes up to this point right here

because in the next one we’re going to start talking about inference rules

and sorry we’re going to start talking about direct proofs and we’re going to

actually start making proofs so make sure and get these inference rules under

your belt and practice working with them and i’ll see you in the next

if you like this video please press this

button and subscribe to my channel now i want to turn it over to you math can be

00:28

difficult because it requires time and energy to become skills i want you to

tell everyone what you do to succeed in your studies either way let us know what

you think in the comments