Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    Predicate Logic 18. Free and Bound Variables: The Lecture

    Uploaded by

    Nidhi Divechavalu
    1) Variables in predicate logic can be either free or bound. An occurrence of a variable within the scope of a quantifier is considered bound, while other occurrences are free. 2) Whether an assignment satisfies a formula depends only on the values of free variables in the formula, not bound variables. 3) Formulas with no free variables are called sentences. Sentences are either true or false in a structure depending on whether assignments satisfy them. If a sentence is true in a structure, that structure is considered a model of the sentence.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Predicate Logic 18. Free and Bound Variables: The Lecture

    Uploaded by

    Nidhi Divechavalu
    40 views21 pages
    1) Variables in predicate logic can be either free or bound. An occurrence of a variable within the scope of a quantifier is considered bound, while other occurrences are free. 2) Whether an assignment satisfies a formula depends only on the values of free variables in the formula, not bound variables. 3) Formulas with no free variables are called sentences. Sentences are either true or false in a structure depending on whether assignments satisfy them. If a sentence is true in a structure, that structure is considered a model of the sentence.

    Original Description:

    maths logic

    Original Title

    logic

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1) Variables in predicate logic can be either free or bound. An occurrence of a variable within the scope of a quantifier is considered bound, while other occurrences are free. 2) Whether an assignment satisfies a formula depends only on the values of free variables in the formula, not bound variables. 3) Formulas with no free variables are called sentences. Sentences are either true or false in a structure depending on whether assignments satisfy them. If a sentence is true in a structure, that structure is considered a model of the sentence.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    40 views21 pages

    Predicate Logic 18. Free and Bound Variables: The Lecture

    Uploaded by

    Nidhi Divechavalu
    1) Variables in predicate logic can be either free or bound. An occurrence of a variable within the scope of a quantifier is considered bound, while other occurrences are free. 2) Whether an assignment satisfies a formula depends only on the values of free variables in the formula, not bound variables. 3) Formulas with no free variables are called sentences. Sentences are either true or false in a structure depending on whether assignments satisfy them. If a sentence is true in a structure, that structure is considered a model of the sentence.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 21

    Predicate Logic

    18. Free and bound variables

    The Lecture
    Free and bound

    Last
    Jouko Väänänen: Propositional logic viewed
    Free and bound

    ! Variables play two different roles in


    predicate logic.
    ! The meaning of !x(xEy) is that y has a
    neighbor. This is a property of y and
    may be true or false depending on what
    y is.
    ! The role of x in !x(xEy) is to bind the
    quantifier !x and the formula xEy
    together.
    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 1

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 1
    ! Every occurrence of a variable x in a formula
    of the form !xB or of the form "xB is called a
    bound occurrence. Occurrences which are not
    bound are called free.

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 1
    ! Every occurrence of a variable x in a formula
    of the form !xB or of the form "xB is called a
    bound occurrence. Occurrences which are not
    bound are called free.

    !x(xEy & "z(zEy!z=x))

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 1
    ! Every occurrence of a variable x in a formula
    of the form !xB or of the form "xB is called a
    bound occurrence. Occurrences which are not
    bound are called free.

    !x(xEy & "z(zEy!z=x))

    Bound occurrence

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 2

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 2

    !x(xEy & !y(¬yEx))

    Last
    Jouko Väänänen: Propositional logic viewed
    Bound occurrence 2

    !x(xEy & !y(¬yEx))

    y free y bound

    Last
    Jouko Väänänen: Propositional logic viewed
    Assignments and free variables

    Last
    Jouko Väänänen: Propositional logic viewed
    Assignments and free variables
    ! Whether an assignment s satisfies a
    formula in a model or not, depends
    only on the values of s on variables
    that occur free in the formula.

    Last
    Jouko Väänänen: Propositional logic viewed
    Assignments and free variables
    ! Whether an assignment s satisfies a
    formula in a model or not, depends
    only on the values of s on variables
    that occur free in the formula.
    ! Whether s satisfes !x(xEy & !y
    (¬yEx)) or not, depends only on s(y),
    not on s(x).

    Last
    Jouko Väänänen: Propositional logic viewed
    Sentences

    Last
    Jouko Väänänen: Propositional logic viewed
    Sentences

    ! Some formulas have no free variables.


    They are called sentences.

    Last
    Jouko Väänänen: Propositional logic viewed
    Sentences

    ! Some formulas have no free variables.


    They are called sentences.
    ! "y!x(xEy & !z(¬zEx)) is a sentence.

    Last
    Jouko Väänänen: Propositional logic viewed
    Sentences

    ! Some formulas have no free variables.


    They are called sentences.
    ! "y!x(xEy & !z(¬zEx)) is a sentence.
    ! "y!x(xEy & !z(¬zEx)) says of a graph
    that every vertex has a neighbor with a
    non-neighbor.

    Last
    Jouko Väänänen: Propositional logic viewed
    Truth

    Last
    Jouko Väänänen: Propositional logic viewed
    Truth
    ! Sentences are true or false in a
    structure, according to whether some
    (equivalently, all) assignments satisfy
    them.

    Last
    Jouko Väänänen: Propositional logic viewed
    Truth
    ! Sentences are true or false in a
    structure, according to whether some
    (equivalently, all) assignments satisfy
    them.
    ! If a sentence A is true in a structure M,
    the structure M is called a model of the
    sentence A.

    Last
    Jouko Väänänen: Propositional logic viewed
    Truth
    ! Sentences are true or false in a
    structure, according to whether some
    (equivalently, all) assignments satisfy
    them.
    ! If a sentence A is true in a structure M,
    the structure M is called a model of the
    sentence A.
    ! This is denoted M䎼A.

    Last
    Jouko Väänänen: Propositional logic viewed

    You might also like