Logic in math

Discussion in 'Math' started by Ryan\$, Dec 30, 2018.

1. Back to school Member

May 22, 2019
46
6
Oh boy, I feel like this is a trap! My thoughts are no it's not. "∃" is a first order or predicate logic symbol but that seems too obvious. But, you have the expression in quotes so you're mentioning or naming an expression rather than using a qualified equation that may or may not be true. For that reason I would say it is a Propositional statement because of what you wrote above. But, you have the entire expression in quotes including the "=1", so I would say it's not propositional but predicate logic.

How's that? LOL It's been more than 30 years since I've thought about this. What I remember first and foremost was never comprehending the logic used to create a mechanical device for giving change in an old school vending machine.

What about this, from a statement by the OP, " Sir .. Sorry but didnt get ur point .. How if 5>10 then 5>100? Dont make sense"

From the domain of rational numbers: can, if 5 >10 than 5 >100, be a true statement?

2. bogosort Active Member

Sep 24, 2011
338
186
Hopefully, it's a trapdoor that leads to further insight. Remember that the defining characteristic of propositional statements is that they can be associated with a truth value. In an earlier post, I claimed that "∃x∀y(x + y = 1)" over the domain of integers is a propositional statement. In English, it says: "there exists some integer x that, when added to any integer y, the sum is equal to 1". Clearly, there is no such x and the statement is false. By virtue of being of false (or true), this expression of predicate logic is indeed a propositional statement.

What about the expression "∃x∃y(x + y = 1)"? This is also a propositional statement, in fact a true one, as it is trivially easy to find two integers whose sum is 1.

Now, consider "∃x(x + y = 1)". In English, it says: "there exists some integer x such that the sum of x and y equals 1". Can we assign a truth value to this? Well, what do we mean by y? Does it stand for all integers or just a particular one? As we saw above, the truth or falsity of the statement depends precisely on this distinction, and since the expression doesn't tell us, we cannot say whether it is true or false. Thus, because it is missing the defining characteristic of propositional statements, the expression "∃x(x + y = 1)" is not a proposition.

In predicate logic, unquantified variables such as the y in "∃x(x + y = 1)" are called free variables. They are the formal equivalent of "is blue", which has no truth value until we actually specify what the thing is that may or may not be blue. In other words, we have to bind the variable with a particular thing or group of things before we can assign a truth value to it. In technical terms, "x is blue" is a propositional function P(x), which is devoid of meaning until we fix x. Once x is bound -- either by specifying what x is (let x represent "the sky"), or by quantifying it (∃x or ∀x)-- then the propositional function becomes a propositional statement. So, P(x) is not a proposition but ∃xP(x) is, as the x has been fixed, i.e., "there is some x (in the domain of discourse) such that x is blue" is a propositional statement. In the first two examples above, the expressions are propositions because both x and y are bound, while the last expression is not because y is free.

Note that all this free/bound variable business is happening at the higher predicate logic level, but is completely invisible from the perspective of propositional logic. At this lower level, the only thing that matters is whether the expression has a truth value; the fact that we used higher-order logic to affix truth values is coincidental and irrelevant. Likewise, the means by which we know whether "Isaac Newton invented the calculus" is true or not is irrelevant to its status as a propositional statement.

I think it's truly terrific that you're dusting off the cobwebs and re-engaging the subject. Sure, many of the details will have long been forgotten over the course of thirty years, but the important bits -- the way of logical thinking -- is part of you. Exercising those particular neural pathways is a great way to keep the mind sharp!

As for vending machine logic, when I was in school, my final project in digital logic class was designing and building an FPGA-based vending machine. The logic is definitely more complicated -- it's a finite state machine, and FSMs have much more computational power than blocks of simple combinational logic -- but fundamentally the decisions are made at the propositional logic level.

Let P = "5 > 10" and Q = "5 > 100". Then, both P and Q are propositional statements (both happen to be false). Consider the implication P → Q, i.e., "if P, then Q". This is false only when P is true and Q is false; for every other values of P and Q, (P → Q) is true. In particular, it is always true when P is false and, since 5 is not greater than 10 over the rationals, the statement "if 5 > 10, then 5 > 100" must therefore be true. However, since the hypothesis P is false, the statement carries no meaningful information and so we qualify the trueness of the statement by saying that it is vacuously true; it is "true" in form only. Several of the posts in this thread try to explain the intuition behind this, but if you still have doubts feel free to let us know.

3. Back to school Member

May 22, 2019
46
6
Forgive me, it will take some time to absorb everything you wrote but it will get my time.

About the if 5 > 10 than 5 > 100. I asked this because of an experience back in the 70's. GPS and Cruise Missiles were the latest thing and aboard ship we were given a cursory explanation of how they work from General Dynamics and Raytheon techs. They started with "You have to think backwards," and began with navigation and latitude and longitude and said something like greater than or less than is determined by where you're at and where you're going. Then, "for navigation distance doesn't matter, direction does." In explaining how the missile works, and I'm paraphrasing the best I can from memory, numbers work backwards and the event of "0" has the largest value. It was explained that the missile has the ability to self correct its navigation if it gets off course. If it has to correct its navigation it doesn't matter where it's been, only where it's at and where it's going. If "0" was the least value a navigation correction would involve going backward over its flight to make a correction but as said, where it's been doesn't matter to solving the navigation error. Again, all that matters is where it's at and where it's going. For a reason I didn't understand and using our example, if 5 < 10 rather than 5 > 10, navigation would have to be restarted instead of making a correction. The problem with restarting was time and the missile's navigation would never catch up to itself and where it was actually at and would be in a constant loop of restarting for corrections. One of them also said some of NASA's countdown systems work the same way.

I'm sure you understand what they were getting at but I didn't. I just accepted it and hung on to, "Distance doesn't matter, direction does." They never discussed the logic or notation to the navigation programming so I always figured they never expected most of us to fully understand what we were being told. I am thinking now that distance is predicate and direction is propositional with maybe the "0" event being predicate? Than again, this was the mid 70's and missile navigation has probably long ago moved on from then.

4. bogosort Active Member

Sep 24, 2011
338
186
I don't understand that correction system, but if they chose to make a scale with 0 > 1 > 2 > ..., there's nothing logically wrong with it (besides maybe being confusing). In such a system, the statement "if 5 > 10, then 5 > 100" would still be true, though not vacuously so, as in the system of integers.

The important takeaway is that the logic itself -- the syntax and rules of inference -- is just scaffolding. We can write down a bunch of theorems of the logic, but they have no meaning until we apply semantics, i.e., until we provide a domain and imbue all the Ps and Qs and such with information. Different choices for semantics will lead to different models of the logical theory, which can result in different answers to the same question. For instance, in the model of integer arithmetic, the statement P = "1 + 1 = 0" is false. But the same statement is true in the model of Galois fields of two elements (e.g., XOR addition).

When we study formal logic systems, we typically ignore all the semantic details and focus on just the syntactical structure; in other words, we want to learn about the theory and not get bogged down by any one of the infinite models that might apply. As an aid to learning, we may sneak in some semantics by way of "real-life examples", but the structure is the thing. In contrast, a math class will focus almost entirely on semantics, as the model is precisely the thing you're there to learn.

5. Back to school Member

May 22, 2019
46
6
Quickly for now but I think a lot of what we were told or weren't told was a need to know consideration. That's a guess. They also spent some time on explaining GPS and how it's timed which I don't remember much about beyond it was important. Someone did say at the time they wondered if the counting down programming wasn't concurrently run against a counting up program as some kind of equal but opposite reference? I can speculate a logic to that but speculation and gossip was the depth, or lack of it, of the discussions. Our job was fire control for the tests, not to be technicians.