Tillämpad Matematik i programmering

Explore

Hem-labb

Läsuppgift till 31 jan
Läsuppgift till 31 jan

LÄS DENNA TEXT, REFLEKTERA OCH TA HJÄLP AV CHEAT-SHEETET FÖR LOGISKA UTTRYCKEN

What Is Predicate Logic

A predicate is a statement or mathematical assertion that contains variables, sometimes referred to as predicate variables, and may be true or false depending on those variables’ value or values.

For example, let’s suppose we have an inequality where we are stating that the left hand side is greater than or equal to the right hand side.

⁠

Subject Predicate

The predicate refers to the property that the subject of the statement can take on.

Predicate Logic Vs Propositional Logic

But why do we care?

Because predicates, which contain variables, don’t have truth values that can be easily detected, they are not propositions. Therefore, we can’t use propositional logic to draw conclusions.

So, what do we do?

We can assign values to each variable — thus, creating a true or false proposition, as seen in the example below.

⁠

Predicate Logic Examples

But this isn’t always effective or helpful, as we ultimately want the predicate to be factual over a range of elements, not just the ones that we’ve hand-selected.

What Is Quantification?

How do we do this?

We use quantifiers to create propositional functions. This process is called quantification.

Quantifiers express the extent to which a predicate is true over a range of elements.

Typically, numeric phrases tell us how a statement applies to a group, affecting how we negate an assertion.

For example, imagine we have the statement: “Every person who is 21 years of age or older is able to purchase alcohol. Sarah is 21 years old.”

While it would seem logical to conclude that Sarah would then be able to purchase alcohol legally, propositional logic alone is ill-equipped with handling quantified variables, namely, what does “every person” really mean?

As the range of possibilities is too broad, we need to apply one of two types of quantifiers to help us achieve our goal:

Universal Quantifiers

Existential Quantifier

Universal Quantifier

Universal Quantification is the proposition that a property is true for all the values of a variable in a particular domain, sometimes called the domain of discourse or the universe of discourse.

Usually, universal quantification takes on any of the following forms:

P(x) is true for all values of x

For all x, P(x)

For each x, P(x)

For every x, P(x)

Given any x, P(x)

And is symbolically denoted

⁠

Universal Quantification Formula

To determine if it’s a universal quantifier, you want to look for words like all, each, every, any.

Existential Quantifier

Existential quantification is the proposition that a property is true for some value in a particular domain.

Customarily, existential quantification takes on one of the following forms:

There exists an x such that P(x)

There exists an element x in the domain such that P(x)

For some x, P(x)

There is some x such that P(x)

And is symbolically denoted

⁠

Universal Quantification Formula

Examples Of Quantifiers In Use

Suppose we have two predicate variables x and y, where the domain for x is F = {foxes} and y has the domain S = {snails}, where P(x,y) is “Foxes are faster than Snails.”

Now we wish to write the following statement using logical symbolism and quantifiers.

⁠

Translate Universal Quantifiers — Example

⁠

Universal Vs Existential Quantifier — Example

⁠

Existential To Universal Quantifiers Example

Not so bad.

And this means that the truth values of quantified statements can be summarized as follows:

⁠

Quantifiers In Truth Table

Also,

Stanford University⁠

has a PDF guide for exploring further.

Quantifier Negation

Okay, so now let’s learn how we negate a statement with quantifiers.

Remember that negation must have the complete opposite truth value from the original statement. For example, if we had the statement, “3 is a prime number,” which is true, the negation would be “3 is not a prime number,” which is false.

Examples Of Negations

So now, let’s look at quantified statements.

⁠

Circle Shading Unshading — Example

Using the five circles, as seen below, we make the following statement:

“Some circles are shaded.”

What would the negation of this statement be?

“Some circles are not shaded.”

Nope! Because this statement is also true!

Remember, a negation must have the opposite truth value.

The trick is to change from a universal quantifier to an existential quantifier or vice versa, adding a “not” to say, “All circles are not shaded.”

Therefore, the negation of quantification has the following properties:

Negation Of Quantifiers

Let’s negate the following statements with P(x) being “like homework.”

⁠

Negation Of Universal Quantifier

⁠

Negation Of Existential Quantifier

Together we will learn how to negate quantifiers, similar to the examples above, and turn statements into symbols and symbols into English statements.

Atomic Formulas

Before we jump into the video lesson, I want to mention that predicate logic, also called predicate calculus, will consider the notion of atoms or atomic formulas in some textbooks. So, let’s briefly discuss this idea.

A predicate name, followed by a list of variables such as P(x, y), where P is the predicate name, and x and y are variables or terms, is referred to as an atomic formula or atom.

Example Of Atom

For example, suppose M is the predicate representing “man is mortal” and let x be a variable. Then M(x) is an atomic formula meaning “x is mortal.”

So, as we know, a predicate is an expression of one or more variables defined on some domain, and an atom is the most straightforward well-formed formula in logic.

A well-formed formula, sometimes abbreviated to (wff), is obtained by composing atoms with logical connectives and quantifiers. Therefore, a well-formed formula is a predicate with the following properties:

⁠

Atomic Formula WFF

Summary

During this lesson, we will refrain from using the phrases atoms or atomic formulas and simply call them predicates and quantifiers, as is common in most Discrete Mathematics courses. But it is nice to know that predicate logic, which is the study of propositions containing variables, has synonymous terms and properties that can and will be used in future mathematics courses.

Alright, so together in this lesson, we will focus on writing predicates, using quantification to construct well-formed formulas, and using our logic rules to negate statements containing quantifiers.

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.

Läsuppgift till 31 janLäsuppgift till 31 jan

What Is Predicate Logic

Predicate Logic Vs Propositional Logic

What Is Quantification?

Universal Quantifier

Existential Quantifier

Examples Of Quantifiers In Use

Quantifier Negation

Examples Of Negations

Atomic Formulas

Example Of Atom

Summary

Läsuppgift till 31 jan
Läsuppgift till 31 jan