Consider truth assignments involving only the propositional variables x_0,x_1,x_2,x_3 and y_0,y_1,y_2,y_3. Every such truth assignment gives a value of 1 (representing true) or 0 (representing false) to each variable. We can therefore think of a truth assignment τ as determining a four-bit integer x_τ depending on the values given to x_0,x_1,x_2 and x_3, and a four-bit integer y_τ depending on the values given to y_0,y_1,y_2 and y_3.

Graham Beasley 2022-07-17 Answered
Consider truth assignments involving only the propositional variables x 0 , x 1 , x 2 , x 3 and y 0 , y 1 , y 2 , y 3 .
Every such truth assignment gives a value of 1 (representing true) or 0 (representing false) to each variable. We can therefore think of a truth assignment τ as determining a four-bit integer x τ depending on the values given to x 0 , x 1 , x 2 and x 3 , and a four-bit integer x τ depending on the values given to y 0 , y 1 , y 2 and y 3 .
More precisely, with τ ( x i ) being the truth value assigned to x i , we can define the integers x τ = 2 3 τ ( x 3 ) + 2 2 τ ( x 2 ) + 2 1 τ ( x 1 ) + τ ( x 0 ) and y τ = 2 3 τ ( y 3 ) + 2 2 τ ( y 2 ) + 2 1 τ ( y 1 ) + τ ( y 0 )
Write a formula that is satisfied by exactly those truth assignments τ for which x τ > y τ . Your formula may use any of the Boolean connectives introduced so far. Explain how you obtained your formula, and justify its correctness
Am I right in assuming that I would need to construct a formula for every single possibility where x is the greater bit?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Brienueentismvh
Answered 2022-07-18 Author has 11 answers
Step 1
I'm just re-writing my answer from the comments section.
τ is a function that assigns the binary value 0 or 1 to a propositional variable, depending on whether that variable has the truth assignment FALSE or TRUE (respectively).
We then compute the 4-bit integers x τ and y τ as follows:
{ x τ = 2 3 τ ( x 3 ) + 2 2 τ ( x 2 ) + 2 1 τ ( x 1 ) + 2 0 τ ( x 0 ) y τ = 2 3 τ ( y 3 ) + 2 2 τ ( y 2 ) + 2 1 τ ( y 1 ) + 2 0 τ ( y 0 )
Therefore, the most trivial formula that satisfies x τ > y τ will assign:
{ x τ = 2 3 × 1 + 2 2 × 1 + 2 1 × 1 + 2 0 × 1 = 8 + 4 + 2 + 1 = 15 = b i n 1111 y τ = 2 3 × 0 + 2 2 × 0 + 2 1 × 0 + 2 0 × 0 = 0 + 0 + 0 + 0 = 0 = b i n 0000
In other words, we're looking for a logical formula that is true whenever the x i are true and the y i are false. Such a formula is given by:
x 0 x 1 x 2 x 3 ( ¬ y 0 ) ( ¬ y 1 ) ( ¬ y 2 ) ( ¬ y 3 )
where we have used the two Boolean connectives ∧ (AND) and ¬ (NOT). The AND connective yields TRUE if and only if both its arguments are TRUE. The NOT connective flips the truth-value of its argument, i.e. NOT TRUE=FALSE and NOT FALSE=TRUE.
Therefore, it can easily be seen that the formula above, where each element is connected by AND connectives, is true only when each element is TRUE. And in particular, the elements formed by NOT y i are true only when the y i are FALSE.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2022-11-17
Compute summation of modules expression?
In particular, what I want to look at is the sum
k = 1 n ( p k ( mod q ) )
where p , q Z 1 can be assumed to be coprime but it would be best if solved in the fullest generality. In the above expression, n is a variable, p,q are fixed, and a(modb) means taking the representative set { 0 , 1 , 2 , . . . , b 1 }. For example, 7 ( mod 3 ) = 1 is the only value we agree upon and 7 ( mod 3 ) 2.
The problem with this is that the list of representatives are permuted by p and hence the methods presented in the initial link are no longer valid.
It would be nice if we can come up with a closed form, but a really tight upper bound of the expression also works.
asked 2022-09-06
Proving combinatoric identity using vote casting example.
I'm still having trouble giving a combinatorial proof of this identity using the vote casting example:
k = 0 m ( ( n k ) ) = ( ( n + 1 m ) ) , n 0
To me, the right-hand side represents casting m votes for n + 1 candidates, since it's a multiset, that seems like we could cast multiple votes for the same candidate. This is equivalent to sum over all the votes each candidate has received, as on the left-hand side.
Is my interpretation correct? I'm still not pretty sure about why the right-hand side has n+1 candidates, while the left side has n.
asked 2022-07-10
How to show that the complement of Cartesian product of two non-empty sets is not the same as the Cartesian product of their complements?
( A × B ) C = ( A C × B C ) ( A C × B ) ( A × B C )
I wanted to do it like this:
A × B = { ( a , b ) A × B | a A b B }
Taking complement, A × B ¯ = { ( a , b ) A × B | a A b B }
Because ( a , b ) A × B prevents me from going anywhere, I chose to do:
Let A × B X × Y
Then, A × B = { ( a , b ) X × Y | a A b B } and A × B ¯ = { ( a , b ) X × Y | a A b B }
But I'm unsure about the correctness of what I did from here.
A × B ¯ = { ( a , b ) X × Y | ( a A b B ) ( a A b B ) ( a A b B ) }
Therefore, A × B ¯ = { ( a , b ) X × Y | ( a A b B ) } { ( a , b ) X × Y | ( a A b B ) } { ( a , b ) X × Y | ( a A b B ) } which gives
We know A × B A × B.
Hence, A × B ¯ = ( A ¯ × B ¯ ) ( A ¯ × B ) ( A × B ¯ ).
"Derive" instead of "prove" because I don't need to prove the equivalence per se. I'm just trying to see how the LHS can lead to the RHS. I should've been more careful about the wording

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question