Maximum size of a set containing logical expressions

In summary, the conversation discusses the maximum size of a set A of logical expressions that only use the symbols →, p, and q. The questioner has found six different possible truth values but is unsure if this is the maximum size and how to prove it. They propose a method involving using pairs of statements of the form "A_i -> A_j" to generate a larger set and determine the largest possible set of functions involving only p, q, and →.
  • #1
alejandro7
13
0
Hi

Can you please help me with this problem?


"What is the maximum size of a set A of logical expressions that only use →, p, q : each pair of elements of A are not equivalent?"

I've found 6 different possible truth values. Is this the maximum size? If yes, how do I prove it?

Thanks!
 
Physics news on Phys.org
  • #2
alejandro7 said:
I've found 6 different possible truth values.

Perhaps you mean "truth tables".

Is this the maximum size? If yes, how do I prove it?

I haven't worked the problem. I don't see an elegant way to prove it.

If you have a set of truth tables for propositional functions A_1, A_2,..A_N that are each functions of (p,q) then you can attempt to produce functions with a new truth tables by looking at all possible pairs of statements of the form "A_i -> A_j".

Beginning with A_1 = p, A_2= q, N=2, you would examine p ->p , p ->q, q->q, q->p.

Adding any functions that have new truth tables, you form a larger set. Then try to produce new truth tables from the larger set in a similar manner. If you generate a set where no new tables can be produced by the above method, I'd say you have the largest possible set of functions involving only p,q, and ->.
 

Related to Maximum size of a set containing logical expressions

1. What is the maximum size of a set containing logical expressions?

The maximum size of a set containing logical expressions can vary depending on the specific context and constraints. However, in general, the maximum size of a set is determined by the number of distinct elements that can be represented within the limitations of the system or language being used. For example, in propositional logic, the maximum size of a set containing logical expressions is determined by the number of propositional variables and connectives that can be used in a given expression.

2. How is the maximum size of a set containing logical expressions calculated?

The calculation of the maximum size of a set containing logical expressions can be complex and may vary depending on the specific type of logic being used. In propositional logic, the maximum size of a set can be calculated by using the rule of multiplication, which states that if there are n possible choices for the first element of a set, and m possible choices for the second element, then there are n x m possible choices for the entire set. This rule can be applied to each element of the set to determine the overall maximum size.

3. Can the maximum size of a set containing logical expressions be infinite?

In some types of logic, such as first-order logic, the maximum size of a set containing logical expressions can be infinite. This is because first-order logic allows for the use of quantifiers, which can create an infinite number of possible combinations. However, in other types of logic, such as propositional logic, the maximum size of a set is typically finite and can be calculated as described in the previous answer.

4. How does the maximum size of a set containing logical expressions impact computational complexity?

The maximum size of a set containing logical expressions can have a significant impact on computational complexity. In general, the larger the set, the more complex and time-consuming it is to process and analyze. This is especially true in automated reasoning systems, where the size of the set can greatly affect the efficiency and accuracy of the system. Therefore, in certain contexts, it may be necessary to limit the size of a set in order to maintain manageable computational complexity.

5. Are there any strategies for reducing the maximum size of a set containing logical expressions?

Yes, there are several strategies that can be used to reduce the maximum size of a set containing logical expressions. One strategy is to simplify or reduce the number of elements in the set by using logical equivalences or rules of inference. Another strategy is to break up a large set into smaller, more manageable subsets. Additionally, some automated reasoning systems use heuristics or pruning techniques to limit the size of a set in order to improve efficiency and accuracy.

Similar threads

I Implication, Boolean Expression and Venn Diagrams
    • Set Theory, Logic, Probability, Statistics
Replies
12
Views
5K
A What is the Probability of Sampling a Set with a Certain Size?
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
I Computer languages as examples in formal logic
    • Set Theory, Logic, Probability, Statistics
2
Replies
40
Views
6K
MHB Upper Bound of Sets and Sequences: Analyzing Logic
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
A Number of unequal integers with sum S
    • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
I Sampling theory and random sample
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
672
I Understanding 2 equivalent formulations of both data set measures
    • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
MHB More Logic statements and arguments
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
I Direct limit of multiverse models of ZFC
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
I Error(?) in proof that the rational numbers are denumerable
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
980

Hot Threads

Recent Insights

Back
Top