How to write predicate logic to express the following relationships.
Rxy is irreflexive
Rxy is intransitive
Rxy is not a partial order
Just need to express the following above relationships with predicate logic and quantifiers.
CodePudding user response:
A relation is reflexive when xRx for all x. In predicate logic, we might write forall x . xRx
. Now, irreflexive might mean two things: either that the relation simply isn't reflexive, or that there are no elements at all related to themselves. These have different predicate logic sentences: exists x . not xRx
, vs forall x . not xRx
.
A relation is transitive when xRy and xRz implies xRz for all x, y and z. In predicate logic, we might write forall x. forall y. forall z. (xRy and yRz) implies xRz.
Again, we might understand by intransitive either that R is simply not transitive, or that there are no x, y and z that have xRy, yRz and xRz true simultaneously; these have predicate logic sentences exists x. exists y. exists z. xRy and yRz and not xRz
and forall x. forall y. forall z. not (xRy and yRz and xRz)
, respectively.
A relation is a partial order when it is reflexive, anti-symmetric and transitive (at least, using the definition here, reasonable people may use variations:https://www.geeksforgeeks.org/partial-order-relation-on-a-set/). We could write this as one big predicate logic sentence like forall x. forall y. forall z. xRx and not (x =/= y and xRy and yRx) and ((xRy and yRz) implies xRz)
. The negation of this just changes the forall
to exists
and not
's the condition (this is a general rule): exists x. exists y. exists z. not [xRx and not (x =/= y and xRy and yRx) and ((xRy and yRz) implies xRz)]
. The not
'ed condition can be simplified using De Morgan's law if desired.
Note: "irreflexive" and "intransitive" probably just mean "not reflexive" and "not transitive", seems that the words for the other things are "antireflexive" and "antitransitive" maybe.