3. Propositional Encodings_ SAT_Problem (25 pts. total) Consider the following rules and definitions for a sports league scheduling problem (even) teams, and every two teams play each other exactly once during season . The season lasts (N-1) weeks. Every team plays one game in each week of the season. . There are N/2 periods or slots per week; every slot is scheduled for one game. For example, a valid schedule for 8 teams named 0,1,2,3,4,5,6,7 would be given by filling in the 4 slots for each week as follows: Slot1 | Slot2 | Slot3 | Slot4 Week10 vs 12 vs 34 vs 56 vs 7 Week20 vs 2 1 vs 73 vs 5 4 vs6 Week34 vs 70 vs 31 vs 62 vs!5 Week4 3 vs 65 vs 70 vs 4 1 vs 2 etc. Encode the Sports League Scheduling problem as a Boolean satisfiability problem. Hints In order to model that two different teams play each other in a given slot, divide each slot in two subslots. For each week, we have N subslots. Adopt the convention that two teams that play consecutive sublots_an odd numbered subslot followed by an even subslot _ in fact play each other. * Variable Xjk is assigned True iff team i plays in subslot j in week k Variable Yijk is assigned True iff team i plays team j in week k (a) (5 pts.) Give the clauses that state that exactly one team plays in each subslot. How many clauses are there? (Note: big-O notation is fine.) (b) (5 pts.) Give the clauses that state that a team plays at most once a week. How many clauses are there? Given these clauses and the previous set, does this imply that each team plays exactly once per week? Explain (c) (5 pts.) Give the clauses that relate the X variables with the Y variables (d) (5 pts.) Give the clauses that state that each pair of teams plays each other exactly once during the season. How many clauses are there? (e) (5 pts.) Of the above sets of clauses, which ones are redundant, if any? Explain