Does Rearranging Quantifiers Affect Looping in Nested Statements?

  • Context: Undergrad 
  • Thread starter Thread starter SamitC
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the impact of rearranging quantifiers in nested statements, specifically in the context of logical expressions involving students and faculty in a school setting. The expressions provided, such as ∃x [S(x) ∧ ∀y {F(y) → ¬ A(x, y)}] and ∃x [S(x) ∧ ¬∃y {F(y) ∧ A(x, y)}], demonstrate that rearranging quantifiers does not change the meaning in this case. However, it can complicate readability and understanding due to the need to track multiple variables and their quantifiers. While no definitive examples were provided where rearranging quantifiers changes the outcome, the potential for such cases exists.

PREREQUISITES
  • Understanding of first-order logic and quantifiers
  • Familiarity with logical expressions and their syntax
  • Basic knowledge of predicate logic involving variables
  • Experience with mathematical reasoning and proofs
NEXT STEPS
  • Study the implications of quantifier placement in first-order logic
  • Explore examples of logical expressions where rearranging quantifiers affects outcomes
  • Learn about the readability and clarity of logical statements in mathematical writing
  • Investigate the role of quantifiers in computational logic and programming languages
USEFUL FOR

Students of mathematics, computer science professionals, and anyone interested in logical reasoning and the structure of logical statements will benefit from this discussion.

SamitC
Messages
36
Reaction score
0
Hello,
Suppose a problem statement is :

In a school, suppose S(x) is “x is a student”, F(x) is “x is a faculty member” and A (x, y) is “x asked a question to y”. Domain is all the people associated with the school. Write the following using quantifiers:
"Some student did not ask any faculty member a question".

Answers are:

So, ∃x [S(x) ∧ ∀y {F(y) → ¬ A(x, y)}] OR ∃x [S(x) ∧ ¬∃y {F(y)A(x, y)}]

Instead, if we bring all the quantifiers at the front, will it cause any difference? Like:
xy [S(x) ∧ {F(y) → ¬ A(x, y)}] OR ∃x ¬∃y [S(x) ∧ {F(y)A(x, y)}]

In general, does it ever cause any change in looping if we bring all quantifiers at the front? Or is there any specific reason not to put all quantifiers at the front?

Thanks
 
Physics news on Phys.org
In this case it doesn't make a difference, but sometimes it can make the expressions harder to read because you have to remember all the variables and their quantifiers before they are actually used.

There could be expressions where it makes a difference, although I don't have an example right now.
 
  • Like
Likes   Reactions: SamitC
mfb said:
In this case it doesn't make a difference, but sometimes it can make the expressions harder to read because you have to remember all the variables and their quantifiers before they are actually used.

There could be expressions where it makes a difference, although I don't have an example right now.
Thank you.
 

Similar threads

  • · Replies 10 ·
Replies
10
Views
1K
  • · Replies 14 ·
Replies
14
Views
4K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
2
Views
6K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 25 ·
Replies
25
Views
905