Logic is not paid attention much in Computer Science. It may be, but as a college kid, I only recently explored it because my professor lent me a book.. I read it while dealing with interpersonal issues that unfortunately these logic can't solve because this is the kind of logic I will not be discussing here.
Logic is at the foundation of both mathematics and computer science. Whether you are writing code, proving theorems, or designing algorithms, you will often use logical concepts like predicates, sets, and the ideas of "some" and all.
Now, one may ask: why bother with logic at all? True, it’s not as immediately necessary as eating or drinking, but if a practice grounds you in reality, then theory makes you a better debugger.
These logic are good at formalizing human language into a set of instructions a computer can understand. This is what logic all about.
Predicate
Predicate is a math construct and a function that treurns true or false based on a property.
P:x -> {true, false}
Say, P(x): "x is an even number"
Then, P(4) -> True. P(5) -> false
A predicate is concerned only with whether a property holds (true/false) for a given input. It doesn’t care about the internal computation or method used to determine the truth.
In code, predicates are typically implemented as boolean functions. Though, the function still does compute something under the good, it just doesn't matter for the logical concept.
def is_even(x):
return x % 2 == 0
Predicates can be classified into two types: concrete and abstract. A concrete predicate directly evaluates a specific property of its input. For example, the function is_even(x) checks whether a number is divisible by 2, producing a straightforward true or false result. In contrast, an abstract predicate describes a property without specifying exactly how to verify it. It’s more conceptual and often used in theory or higher-level reasoning. For instance, the statement “x is prime” can be treated as a predicate even before we define the exact algorithm to check it.
Implication
Once we have predicates, or simple propositions, we often want to describe how one statement implies another. In logic, this is called an implication.
Formally, an implication P ⇒ Q (“P implies Q”) means that if P is true, then Q must also be true.
P => Q ("P implies Q")
Some readers may connect the dot, and see that this is similar to propositional logic.
Anyway, in programming, this concept maps directly to conditional statement like if statement.
def check_even_and_print(x):
if x % 2 == 0: # P: x is even
print(f"{x} is even") # Q: print statement executes
Even more generally, any if-else logic in programming is a way of encoding implications and conditional reasoning.
Set
Predicates are untyped by default. In theory, they can take any kind of inputs. However, in practice, we often want to restrict the types of inputs a predicate can take.
Sets are used to restrict the type of input.
"c is a computer" -> c ∈ Computer
Here, c belongs to the set of all computers. Sets allow us to define the domain of discourse, which is the collection of all objects we are considering for a particular discussion or predicate.
In sets, there is something called "domain of discourse". What that means is that predicates themselves should not be part of the domain of discourse, because this can lead to paradoxes and mathematical complications. The domain should contain only the objects the predicates are describing, not the predicates themselves.
"Some" and "All"
After defining predicates and sets, we often want to make statements about some or all elements of a set. This is where quantifiers come in.
The universal quantifier, written as ∀x ∈ S, P(x), expresses that a predicate is true for every element in a set.
The existential quantifier, written as ∃x ∈ S, P(x), expresses that a predicate is true for at least one element in a set.
In programming, quantifiers often appear implicitly when we work with loops and conditional statements.
To check if a predicate holds for all elements in a list or set, we loop through each element and ensure the condition is true for every item.
numbers = [2, 4, 6, 8]
all_even = all(x % 2 == 0 for x in numbers)
print(all_even)
Here, all() checks the predicate for every element, just like the universal quantifier.
To check if a predicate holds for at least one element, we loop until we find a matching item.
numbers = [1, 3, 4, 7]
some_even = any(x % 2 == 0 for x in numbers)
print(some_even)
Here, any() returns true as soon as it finds an element that satisfies the predicate, mirroring the existential quantifier.
Practical
Now that we have learned about predicates, implication, sets, and quantifiers, let's try making a simple login system by combining all of them.
First, let's define our sets. The set of all registered users (domain) could be like this:
users = {
"alice": "password123",
"bob": "qwerty"
}
We need two conditions to check if the user is registered, and that if the password matches to where it is being stored. These will be our predicates.
`def is_registered(user):
return user in users
def password_matches(user, pwd):
return users.get(user) == pwd`
Here comes the implication, if-then logic. We only check the password if the user is registered:
if is_registered(username):
if password_matches(username, password):
print("Login successful")
else:
print("Incorrect password")
else:
print("User not found")
Here, the implication is_registered(username) ⇒ password_matches(username, password) is implemented as a conditional: we only evaluate the second part if the first is true.
As for quantifiers, these can be used when we want to extend the system. Say, Universal quantifier (all) ensure that all passwords meet a security requirement.
all(len(p) >= 8 for p in users.values()) # ∀ password, length >= 8
Existential quantifier (some) can check if at least one user has admin privileges.
some_admin = any(user == "admin" for user in users) # ∃ user, admin
By combining these four concepts, we can formalize, reason about, and implement logic safely in a program. Predicates let us define conditions, implication guides conditional actions, sets define our domain, and quantifiers allow reasoning about collections of data. This is exactly how mathematical logic translates into practical computer science.
Top comments (0)